Almost Perfect

题意翻译

对于排列 $p$，我们称它是基本完美的，当且仅当排列 $p$ 的逆，$q$，满足 $\forall 1\le i\le n,|p_i-q_i|\le 1$。一个排列的逆是满足 $\forall 1\le i\le n,q_{p_i}=i$ 的唯一排列。 输出 $1\sim n$ 的基本完美排列的数量，对 $998244353$ 取模。 本题多测。 数据范围：$T\le 1000$，$1\le n,\sum n\le 3\times 10^5$。

题目描述

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

3
2
3
50

输出样例 #1

2
4
830690567

说明

For $ n = 2 $ , both permutations $ [1, 2] $ , and $ [2, 1] $ are almost perfect. For $ n = 3 $ , there are only $ 6 $ permutations. Having a look at all of them gives us: - $ [1, 2, 3] $ is an almost perfect permutation. - $ [1, 3, 2] $ is an almost perfect permutation. - $ [2, 1, 3] $ is an almost perfect permutation. - $ [2, 3, 1] $ is NOT an almost perfect permutation ( $ \lvert p_2 - p^{-1}_2 \rvert = \lvert 3 - 1 \rvert = 2 $ ). - $ [3, 1, 2] $ is NOT an almost perfect permutation ( $ \lvert p_2 - p^{-1}_2 \rvert = \lvert 1 - 3 \rvert = 2 $ ). - $ [3, 2, 1] $ is an almost perfect permutation. So we get $ 4 $ almost perfect permutations.