T533501 「GFOI Round 2」Aob & Blice (English ver.)

**[Chinese statement](https://www.luogu.com.cn/problem/P11281). You must submit your code at the Chinese version of the statement.**

Aob and Blice are playing a game. There is a permutation $p$ of length $n$, and both Aob and Blice each hold an initially empty **distinct** set, denoted as $S_A$ and $S_B$ respectively. The rules for one round of the game are as follows: - First, Aob **randomly** selects two integers $x$ and $y$ such that $1 \leq x < y \leq n$ and $p_x > p_y$. Then, Aob **randomly** chooses one of the two **ordered pairs** $(x, y)$ or $(p_x, p_y)$ to add to his set $S_A$. - After that, Blice must choose one of the pairs $(y, x)$ or $(p_y, p_x)$ to add to her set $S_B$. **Note that $x$ and $y$ are the same as those chosen by Aob in the previous step.** After infinitely many rounds $^{\dagger}$, Aob and Blice will compare their sets. Although Aob plays randomly, Blice is smarter and hopes to make both sets exactly the same in the end, so the game will end in a tie—this way, neither of them will be upset! Unfortunately, some elements in the permutation have disappeared. Blice has asked for your help to determine how many possible original permutations could allow them to achieve a tie after infinitely many rounds. For convenience, you only need to compute the answer modulo $998244353$. --- $^{\dagger}$ A tie after infinitely many rounds is defined as follows: for any $\varepsilon > 0$, there exists a positive integer $N$ such that for all $n > N$, Blice can adopt a strategy ensuring that the probability of not achieving a tie after $n$ rounds is less than $\varepsilon$.

无

无

#### Sample $1$ Explanation Exactly two permutations are valid: $\{1,2,3\},\{3,2,1\}$. #### Subtasks and Constraints | Subtask ID | $n \leq$ | Special Properties | Score | | :----------: | :----------: | :----------: | :----------: | | 1 | $9$ | No | $20$ | | 2 | $2000$ | A | $15$ | | 3 | $2000$ | No | $10$ | | 4 | $10^6$ | A | $15$ | | 5 | $10^6$ | B | $10$ | | 6 | $10^6$ | No | $30$ | - Special Property A: $p_i \ne 0$. - Special Property B: $p_i = 0$. For all tests, it is guaranteed that: - $1 \le n \le 10^6$; - $0 \le p_i \le n$; - For all $1 \le i < j \le n$, if $p_i \ne 0$ and $p_j \ne 0$, then $p_i \ne p_j$.