A15286 | $Almost Perfect$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

A permutation $p$ of length $n$ is called almost perfect if for all integer $1 \leq i \leq n$ , it holds that $\lvert p_i - p^{-1}_i \rvert \le 1$ , where $p^{-1}$ is the inverse permutation of $p$ (i.e. $p^{-1}_{k_1} = k_2$ if and only if $p_{k_2} = k_1$ ). Count the number of almost perfect permutations of length $n$ modulo $998244353$ .

The first line contains a single integer $t$ ( $1 \leq t \leq 1000$ ) — the number of test cases. The description of each test case follows. The first and only line of each test case contains a single integer $n$ ( $1 \leq n \leq 3 \cdot 10^5$ ) — the length of the permutation. It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$ .

For each test case, output a single integer — the number of almost perfect permutations of length $n$ modulo $998244353$ .

输入 #1

输出 #1

2
4
830690567

C++ 编辑器

输入

输出