I. Short Permutation Problemtime limit per test7 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputXomu - Last Dance⠀You are given an integer n.For each (m, k) such that 3 \leq m \leq n+1 and 0 \leq k \leq n-1, count the permutations of [1, 2, ..., n] such that p_i + p_{i+1} \geq m for exactly k indices i, modulo 998\,244\,353.InputThe input consists of a single line, which contains two integers n, x (2 \leq n \leq 4000, 1 \leq x < 1\,000\,000\,007).OutputLet a_{m,k} be the answer for the pair (m, k), modulo 998\,244\,353.Let \large S = \sum_{m=3}^{n+1} \sum_{k=0}^{n-1} a_{m,k}x^{mn+k}\phantom{0}.Output a single line with an integer: S modulo 1\,000\,000\,007.Note that using two different modulos is intentional. We want you to calculate all the a_{m,k} modulo 998\,244\,353, then treat them like integers in the range [0, 998\,244\,352], and hash them modulo 1\,000\,000\,007.ExamplesInput
3 2Output
77824
Input
4 1000000000Output
30984329
Input
8 327869541Output
85039220
Input
4000 1149333Output
584870166
NoteIn the first test case, the answers for all (m, k) are shown in the following table: k = 0k = 1k = 2m = 3006m = 4042   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 = 0k = 1k = 2k = 3m = 300024m = 4001212m = 504164   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 = 0k = 1k = 2k = 3k = 4k = 5k = 6k = 7m = 3000000040320m = 40000001008030240m = 50000014401728021600m = 600004808640216009600m = 700096345616416168963456m = 80048216012960182406480432m = 901611529648186889648115216 
3 2
77824 
['combinatorics', 'dp', 'fft', 'math', '*1900']