D. 移除标记

每次测试时间限制：2 秒
内存限制：256 兆字节

r-906 & Hatsune Miku - All I Can See Is You

题目描述

定义一个整数序列 $a$ 是合法的，当且仅当 $\forall 1 \le i \le n$，有 $0 \le a_i \le i$。

定义合法序列 $a$（长度为 $n$）的权值 $f(a)$ 如下：

• 初始时，在数轴上的闭区间 $[1, n]$ 内的每个整数点上都放置一个标记。
• 按顺序执行 $n$ 次操作。在第 $i$ 次操作中：
  • 如果 $a_i \neq 0$，则在闭区间 $[a_i, i]$ 中移除一个尚未被移除的标记；
  • 如果 $a_i = 0$，则不进行任何操作。
• $f(a)$ 是移除标记的方式数。如果存在某个 $t$，使得两种方式在第 $t$ 次操作中移除的标记位置不同，则认为这两种方式不同。

例如，$f([0,2,1]) = 2$，因为我们可以依次移除位置 $2,1$ 或 $2,3$ 上的标记。

JT 给你两个整数 $n, m$，要求你计算所有长度为 $n$ 的合法序列的权值之和。由于答案可能很大，请对 $m$ 取模后输出。

注意：合法序列的总数为 $(n+1)!$。

输入格式

每个测试文件包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。
接下来 $t$ 行，每行包含两个整数 $n$ 和 $m$（$1 \le n \le 5000$，$10^8 \le m \le 1.01 \cdot 10^9$），分别表示合法序列的长度和模数。

保证所有测试用例的 $n^2$ 之和不超过 $2.5 \cdot 10^7$。

输出格式

对于每个测试用例，输出一个整数，表示所有合法序列的权值之和对 $m$ 取模的结果。

示例

输入：

6
1 1000000007
2 1000000007
3 1000000007
4 1000000007
5 1000000007
114 514191981

输出：

2
7
37
273
2672
393775292

提示

在第一个测试用例中，合法序列为 $[0]$ 和 $[1]$，答案为 $f([0]) + f([1]) = 1 + 1 = 2$。

在第二个测试用例中，合法序列为 $[0,0], [0,1], [0,2], [1,0], [1,1], [1,2]$。
其中 $[0,1]$ 的权值为 $2$，其余序列的权值均为 $1$，所以答案为 $5 \cdot 1 + 1 \cdot 2 = 7$。