Minimum of Degrees

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
There is a graph with N vertices and no edges. Chef is going to add all N*(N1)/2 possible undirected edges to the graph, in a random order. The cost of adding an edge between vertices x and y is equal to min(degree(x), degree(y)). Here, degree(x) denotes the number of edges incident on x before adding the new edge (between x and y).
Find the expected total cost of adding all the edges and print it modulo 998244353. See more details in the output section below.
Input
The input contains a single integer N, denoting the number of vertices.
Output
For the constraints given below, it can be proved that the answer (the expected value of the total cost) can be expressed as a rational P/Q for some integers P and Q, where Q isn't divisible by 998244353. Print one integer: P*Q^{1} modulo 998244353. Here, Q^{1} denotes the modular inverse with respect to 998244353.
Constraints
 2 ≤ N ≤ 300,000
Example
Input1: 3 Output1: 1 Input2: 4 Output2: 199648875
Explanation
Example #1. The graph contains 3 vertices and Chef will add 3 edges. No matter what the order of adding edges is, the cost of adding the first edge is 0 because degrees of vertices are 0 initially. Similarly, the cost of adding the second edge is 0 because at least one of two vertices connected with a new edge has degree 0. Finally, the third edge connects vertices that both have degree 1 after adding first two edges, so the cost is min(1, 1) = 1. The total cost is always 1, so its expected value is 1 as well.
Example #2. There are 4 vertices and Chef will add 6 edges. The answer is 22/5, so you should print 22 * 5^{1} = 22 * 598946612 = 13176825464 = 199648875 (modulo 998244353). Let's analyze one possible scenario:
 Initially, all degrees are equal to 0. Add the edge 23 (an edge between vertices 2 and 3) with cost min(0, 0) = 0.
 Degrees of vertices 1, 2, 3, 4 are 0, 1, 1, 0 respectively. Add the edge 13 with cost min(0, 1) = 0.
 Degrees are 1, 1, 2, 0. Add the edge 14 with cost min(1, 0) = 0.
 Degrees are 2, 1, 2, 1. Add the edge 12 with cost min(2, 1) = 1.
 Degrees are 3, 2, 2, 1. Add the edge 24 with cost min(2, 1) = 1.
 Degrees are 3, 3, 2, 2. Add the edge 34 with cost min(2, 2) = 2.
The total cost in the analyzed scenario is 1 + 1 + 2 = 4.
Author:  errichto 
Tags  errichto 
Date Added:  21062017 
Time Limit:  1.75 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 