/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
(1,2,\ldots,2N) の順列 P=(P_1,P_2,\ldots,P_{2N}) に対し、スコアを以下で定義します。
P を順序を保ったまま二つの長さ N の（連続するとは限らない）部分列 A = (A_1,A_2,\ldots,A_N),B = (B_1,B_2,\ldots,B_N) に分割する。分割を行ったときに得られる \displaystyle\sum_{i=1}^{N}A_i B_i の最大値をスコアとする。
(1,2,\ldots,2N) の順列全てについてスコアを計算し、それらの最大値を M とします。 (1,2,\ldots,2N) の順列のうち、スコアが M であるものの個数を 998244353 で割ったあまりを求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
2
出力例 1
16
考えられる順列 24 通りの中で、スコアの最大値 M は 14 です。スコアが 14 となる順列は 16 通りあります。
例えば、順列 (1,2,3,4) は A=(1,3), B=(2,4) と分割することで、\sum _{i=1}^{N}A_i B_i = 14 となります。
入力例 2
10000
出力例 2
391163238
998244353 で割ったあまりを答えてください。
Score : 600 points
Problem Statement
The score of a permutation P=(P_1,P_2,\ldots,P_{2N}) of (1,2,\ldots,2N) is defined as follows:
Consider dividing P into two (not necessarily contiguous) subsequences A = (A_1,A_2,\ldots,A_N) and B = (B_1,B_2,\ldots,B_N). The score of P is the maximum possible value of \displaystyle\sum_{i=1}^{N}A_i B_i in such a division.
Let M be the maximum among the scores of all permutations of (1,2,\ldots,2N). Find the number, modulo 998244353, of permutations of (1,2,\ldots,2N) with the score of M.
Constraints
- 1 \leq N \leq 2\times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
2
Sample Output 1
16
The maximum among the scores of the 24 possible permutations, M, is 14, and there are 16 permutations with the score of 14.
For instance, the permutation (1,2,3,4) achieves \sum _{i=1}^{N}A_i B_i = 14 in the division A=(1,3), B=(2,4).
Sample Input 2
10000
Sample Output 2
391163238
Print the count modulo 998244353.