I. 短排列问题

时间限制：每个测试点 $7$ 秒
空间限制：每个测试点 $1024$ MB

给定整数 $n$。
对于每一对 $(m,k)$，其中 $3 \le m \le n+1$，$0 \le k \le n-1$，计算 $[1,2,\dots,n]$ 的排列中满足 $p_i + p_{i+1} \ge m$ 的索引 $i$ 恰好有 $k$ 个的排列个数，结果对 $998244353$ 取模。

输入：一行两个整数 $n, x$（$2 \le n \le 4000$，$1 \le x < 10^9+7$）。

输出：令 $a_{m,k}$ 为对应答案（模 $998244353$），计算

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

输出 $S$ 模 $10^9+7$ 的值。注意两个模数不同：$a_{m,k}$ 先模 $998244353$ 视为整数，再代入 $S$ 模 $10^9+7$。

样例

输入

3 2

输出

77824

输入

4 1000000000

输出

30984329

输入

8 327869541

输出

85039220

输入

4000 1149333

输出

584870166

---