给你一个整数$$$n$$$。
对于每个 $$$(m, k)$$$,使得 $$$3 \leq m \leq n+1$$$ 和 $$$0 \leq k \leq n-1$$$,计算 $$$[1, 2, ..., n]$$$ 的排列,使得 $$$p_i + p_{i+1} \geq m$$$ 恰好满足 $$$k$$$ 索引$$$i$$$,模 $$$998\,244\,353$$$。
输入
输入由一行组成,其中包含两个整数 $$$n$$$, $$$x$$$ ($$$2 \leq n \leq 4000$$$, $$$1 \leq x < 1\,000\,000\,007$$$)。
输出
让 $$$a_{m,k}$$$ 为对 $$$(m, k)$$$ 的答案,模 $$$998\,244\,353$$$。
设$$$$$$\large S = \sum_{m=3}^{n+1} \sum_{k=0}^{n-1} a_{m,k}x^{mn+k}\phantom{0}。$$$$$$
输出一行包含一个整数:$$$S$$$ 模 $$$1\,000\,000\,007$$$。
请注意,使用两个不同的模是有意的。我们希望您计算所有 $$$a_{m,k}$$$ 以 $$$998\,244\,353$$$ 为模,然后将它们视为 $$$[0, 998\,244\,352]$$$ 范围内的整数,并以 $$$1\,000\,000\,007$$$ 为模对它们进行哈希处理。
示例
输入 #1
3 2
输出 #1
77824
输入 #2
4 1000000000
输出 #2
30984329
输入 #3
8 327869541
输出 #3
85039220
输入#4
4000 1149333
输出#4
584870166
注意
在第一个测试用例中,所有 $$$(m, k)$$$ 的答案如下表所示:
$$$k = 0$$$$$$k = 1$$$$$$k = 2$$$$$$m = 3$$$$$$0$$$$$$0$$$$$$6$$$$$$m = 4$$$$$$0$$$$$4$$$$$$2$$$
- $$$(m, k) = (3, 2)$$$ 的答案是 $$$6$$$,因为对于长度 $$$3$$$ 的每个排列,$$$a_i + a_{i+1} \geq 3$$$ 正好是 $$$2$$$ 次。
- $$$(m, k) = (4, 2)$$$ 的答案是 $$$2$$$。事实上,存在长度 $$$3$$$ 的 $$$2$$$ 排列,使得 $$$a_i + a_{i+1} \geq 4$$$ 恰好是 $$$2$$$ 次:$$$[1, 3, 2]$$$,$$$[2, 3, 1]$$$。
因此,要打印的值为 $$$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)$$$。
在第二个测试用例中,所有$$$(m, k)$$$的答案如下表所示:
$$$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$$$
- $$$(m, k) = (5, 1)$$$ 的答案是 $$$4$$$。事实上,存在 $$$4$$$ 长度 $$$4$$$ 的排列,使得 $$$a_i + a_{i+1} \geq 5$$$ 正好 $$$1$$$ 时间: $$$[2, 1, 3, 4]$$$, $$$[3, 1, 2, 4]$$$, $$$[4, 2, 1, 3]$$$, $$$[4,3,1,2]$$$。
在第三个测试用例中,所有$$$(m, k)$$$的答案如下表所示:
$$$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$$$