E. Almost Perfect
combinatorics; fft; math
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\).
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.