Permutation Cut Profiles - Repovive Premier Round 5 | Repovive

13G. Permutation Cut Profiles

3500 pts2s256 MB

For a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ , define an array $A$ of length $n-1$ as follows.

Initially, all elements of $A$ are equal to $0$ .

For each adjacent pair $p_j, p_{j+1}$ , let $l = \min(p_j, p_{j+1})$ and $r = \max(p_j, p_{j+1})$ . Then, for every $i$ with $l \le i < r$ , increase $A_i$ by $1$ .

You are given $n$ . Find the number of different arrays $A$ that can be obtained from at least one permutation of $1, 2, \ldots, n$ .

Output the answer modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

Case 4

Case 5

Explanation

Case 1

The array $A$ has length $0$ , so there is only one possible array: the empty array.

Case 2

The only possible array is $[1]$ .

Case 3

The possible arrays are $[1,1]$ , $[1,2]$ , and $[2,1]$ .

Case 4

There are $10$ different arrays. For example, $[1,1,1]$ is obtained from the permutation $1,2,3,4$ , and $[1,3,2]$ is obtained from the permutation $1,4,2,3$ .

Case 5

After removing duplicates among all permutations, $32$ different arrays remain. For example, $[1,1,1,1]$ and $[1,3,3,1]$ are both possible.

Output

Case 1

Case 2

Case 3

Case 4

Case 5

For a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ , define an array $A$ of length $n-1$ as follows.

Initially, all elements of $A$ are equal to $0$ .

For each adjacent pair $p_j, p_{j+1}$ , let $l = \min(p_j, p_{j+1})$ and $r = \max(p_j, p_{j+1})$ . Then, for every $i$ with $l \le i < r$ , increase $A_i$ by $1$ .

You are given $n$ . Find the number of different arrays $A$ that can be obtained from at least one permutation of $1, 2, \ldots, n$ .

Output the answer modulo $998244353$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

The array $A$ has length $0$ , so there is only one possible array: the empty array.

The only possible array is $[1]$ .

The possible arrays are $[1,1]$ , $[1,2]$ , and $[2,1]$ .

There are $10$ different arrays. For example, $[1,1,1]$ is obtained from the permutation $1,2,3,4$ , and $[1,3,2]$ is obtained from the permutation $1,4,2,3$ .

After removing duplicates among all permutations, $32$ different arrays remain. For example, $[1,1,1,1]$ and $[1,3,3,1]$ are both possible.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

13G. Permutation Cut Profiles

Constraints

Input

Output

Samples

13G. Permutation Cut Profiles

Constraints

Input

Output

Samples