定义整数序列 $$$a$$$ 有效 当且仅当 $$$\forall 1 \le i \le n, 0 \le a_i \le i$$$。
定义 重量 $$$f(a)$$$ 的 有效 序列 $$$a$$$,长度为 $$$n$$$:
- 最初,在数轴上闭合线段 $$$[1, n]$$$ 中的每个整数点放置一个标记。
- 按顺序执行 $$$n$$$ 操作。在第 $$$i$$$ 次操作过程中,如果 $$$a_i \ne 0$$$,则移除闭合段 $$$[a_i, i]$$$ 中尚未移除的 token;否则,什么也不做。
- $$$f(a)$$$ 是删除标记的方法数量。如果存在$$$t$$$,使得在第$$$t$$$操作中这两种方式删除的标记的位置不同,则认为两种方式是不同的。
例如,$$$f([0, 2, 1]) = 2$$$,因为我们可以依次删除$$$2, 1$$$ 或$$$2, 3$$$ 上的标记。
JT 给你两个整数 $$$n, m$$$ 并要求你求它们的总和 重量全部$$$(n + 1)!$$$ 有效 长度为 $$$n$$$ 的序列。由于答案可能太大,请打印它对 $$$m$$$ 取模。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 5000, 10^8 \le m \le 1.01 \cdot 10^9$$$) — 的长度 有效 序列和模数。
保证所有测试用例的 $$$n^2$$$ 总和不超过 $$$2.5 \cdot 10^7$$$。
输出
对于每个测试用例,输出一个整数—— 重量全部$$$(n + 1)!$$$ 有效 长度为 $$$n$$$ 的序列,以 $$$m$$$ 为模。
示例
输入复制
61 10000000072 10000000073 10000000074 10000000075 1000000007114 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$$$。