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.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

13G. Permutation Cut Profiles

Constraints

Input

Output

Samples

13G. Permutation Cut Profiles

Constraints

Input

Output

Samples