I. 短排列问题

每个测试的时间限制：$7$ 秒
每个测试的内存限制：$1024$ MB

---

给定一个整数 $n$。

对于每个满足 $3 \le m \le n+1$ 且 $0 \le k \le n-1$ 的 $(m,k)$，统计 $[1,2,\ldots,n]$ 的所有排列中，使得 $p_i + p_{i+1} \ge m$ 恰好有 $k$ 个下标 $i$ 的排列个数，结果对 $998244353$ 取模。

---

输入

输入只有一行，包含两个整数 $n, x$（$2 \le n \le 4000$，$1 \le x < 1000000007$）。

---

输出

设 $a_{m,k}$ 为对 $(m,k)$ 的答案（已对 $998244353$ 取模）。
定义

$$S = \sum_{m=3}^{n+1} \sum_{k=0}^{n-1} a_{m,k} \, x^{mn+k}. $$

输出一行一个整数：$S$ 对 $1000000007$ 取模的结果。

注意，使用两个不同的模数是故意的。我们需要你先计算所有 $a_{m,k}$ 对 $998244353$ 取模的结果，然后将它们视为 $[0,998244352]$ 范围内的整数，再对 $1000000007$ 取模得到哈希值。

---

示例

输入

3 2

输出

77824

在第一个测试用例中，所有 $(m,k)$ 的答案如下表所示：

$m$ \ $k$	$k=0$	$k=1$	$k=2$
$m=3$	$0$	$0$	$6$
$m=4$		$4$	$2$

• $(m,k)=(3,2)$ 的答案为 $6$，因为对于长度为 $3$ 的每个排列，$a_i+a_{i+1}\ge 3$ 恰好发生 $2$ 次。
• $(m,k)=(4,2)$ 的答案为 $2$。事实上，有 $2$ 个长度为 $3$ 的排列使得 $a_i+a_{i+1}\ge 4$ 恰好发生 $2$ 次：$[1,3,2]$、$[2,3,1]$。

因此，需要输出的值为

$$2^9\cdot0 + 2^{10}\cdot0 + 2^{11}\cdot6 + 2^{12}\cdot0 + 2^{13}\cdot4 + 2^{14}\cdot2 \equiv 77824 \pmod{1000000007}. $$

---

输入

4 1000000000

输出

30984329

在第二个测试用例中，所有 $(m,k)$ 的答案如下表所示：

$m$ \ $k$	$k=0$	$k=1$	$k=2$	$k=3$
$m=3$	$0$	$0$	$0$	$24$
$m=4$			$12$
$m=5$		$4$	$16$	$4$

• $(m,k)=(5,1)$ 的答案为 $4$。事实上，有 $4$ 个长度为 $4$ 的排列使得 $a_i+a_{i+1}\ge 5$ 恰好发生 $1$ 次：$[2,1,3,4]$、$[3,1,2,4]$、$[4,2,1,3]$、$[4,3,1,2]$。

---

输入

8 327869541

输出

85039220

在第三个测试用例中，所有 $(m,k)$ 的答案如下表所示：

$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$							$10080$	$30240$
$m=5$						$1440$	$17280$	$21600$
$m=6$					$480$	$8640$	$21600$	$9600$
$m=7$				$96$	$3456$	$16416$	$16896$	$3456$
$m=8$			$48$	$2160$	$12960$	$18240$	$6480$	$432$
$m=9$		$16$	$1152$	$9648$	$18688$	$9648$	$1152$	$16$

---

输入

4000 1149333

输出

584870166