CF1909I Short Permutation Problem

给定一个正整数 $n$，对于满足 $3\le m\le n+1,0\le k\le n-1$ 的所有二元组 $(m,k)$，求满足有恰好 $k$ 个 $i$ 满足 $p_i+p_{i+1}\ge m$ 的 $1\sim n$ 的排列 $p$ 的数量，模 $998244353$。

无

无

In the first test case, the answers for all $ (m, k) $ are shown in the following table: $ k = 0 $ $ k = 1 $ $ k = 2 $ $ m = 3 $ $ 0 $ $ 0 $ $ 6 $ $ m = 4 $ $ 0 $ $ 4 $ $ 2 $ - The answer for $ (m, k) = (3, 2) $ is $ 6 $ , because for every permutation of length $ 3 $ , $ a_i + a_{i+1} \geq 3 $ exactly $ 2 $ times. - The answer for $ (m, k) = (4, 2) $ is $ 2 $ . In fact, there are $ 2 $ permutations of length $ 3 $ such that $ a_i + a_{i+1} \geq 4 $ exactly $ 2 $ times: $ [1, 3, 2] $ , $ [2, 3, 1] $ . Therefore, the value to print is $ 2^9 \cdot 0 + 2^{10} \cdot 0 + 2^{11} \cdot 6 + 2^{12} \cdot 0 + 2^{13} \cdot 4 + 2^{14} \cdot 2 \equiv 77\,824 \phantom{0} (\text{mod} \phantom{0} 1\,000\,000\,007) $ . In the second test case, the answers for all $ (m, k) $ are shown in the following table: $ k = 0 $ $ k = 1 $ $ k = 2 $ $ k = 3 $ $ m = 3 $ $ 0 $ $ 0 $ $ 0 $ $ 24 $ $ m = 4 $ $ 0 $ $ 0 $ $ 12 $ $ 12 $ $ m = 5 $ $ 0 $ $ 4 $ $ 16 $ $ 4 $ - The answer for $ (m, k) = (5, 1) $ is $ 4 $ . In fact, there are $ 4 $ permutations of length $ 4 $ such that $ a_i + a_{i+1} \geq 5 $ exactly $ 1 $ time: $ [2, 1, 3, 4] $ , $ [3, 1, 2, 4] $ , $ [4, 2, 1, 3] $ , $ [4, 3, 1, 2] $ . In the third test case, the answers for all $ (m, k) $ are shown in the following table: $ k = 0 $ $ k = 1 $ $ k = 2 $ $ k = 3 $ $ k = 4 $ $ k = 5 $ $ k = 6 $ $ k = 7 $ $ m = 3 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 40320 $ $ m = 4 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 10080 $ $ 30240 $ $ m = 5 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 1440 $ $ 17280 $ $ 21600 $ $ m = 6 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 480 $ $ 8640 $ $ 21600 $ $ 9600 $ $ m = 7 $ $ 0 $ $ 0 $ $ 0 $ $ 96 $ $ 3456 $ $ 16416 $ $ 16896 $ $ 3456 $ $ m = 8 $ $ 0 $ $ 0 $ $ 48 $ $ 2160 $ $ 12960 $ $ 18240 $ $ 6480 $ $ 432 $ $ m = 9 $ $ 0 $ $ 16 $ $ 1152 $ $ 9648 $ $ 18688 $ $ 9648 $ $ 1152 $ $ 16 $