考虑从 1 到 $$$n$$$ 的整数的排列 $$$p_1, p_2, \dots p_n$$$。我们将排列的子段 $$$p_l, p_{l+1}, \dots, p_{r-1}, p_{r}$$$ 称为 间隔 如果它是某些连续整数集的重新排序。例如,排列 $$$(6,7,1,8,5,3,2,4)$$$ 具有区间 $$$(6,7)$$$、$$$(5,3,2,4)$$$、$$$(3,2)$$$ 等。
每个排列都有一些琐碎的间隔 - 完整排列本身和每个元素。我们称之为排列 无间隔 如果它没有非平凡间隔。换句话说,无区间排列的长度区间不介于 2 和 $$$n - 1$$$ 之间(包括 2 和 $$$n - 1$$$)。
你的任务是计算长度 $$$n$$$ 模素数 $$$p$$$ 的无区间排列的数量。
输入
在输入的第一行中有两个整数 $$$t$$$ ($$$1 \le t \le 400$$$) 和 $$$p$$$ ($$$10^8 \le p \le 10^9$$$) - 要解决的测试用例数量和素数模。在接下来的 $$$t$$$ 行中,有一个整数 $$$n$$$ ($$$1 \le n \le 400$$$) — 排列的长度。
输出
对于每个 $$$t$$$ 测试用例,打印一个整数 - 以 $$$p$$$ 为模的无区间排列数。
示例
输入复制
4 998244353 1 4 5 9
输出复制
1 2 6 28146
输入复制
1 437122297 20
输出复制
67777575
注意
对于 $$$n = 1$$$ ,唯一的排列是无区间的。对于 $$$n = 4$$$,两个无区间排列是 $$$(2,4,1,3)$$$ 和 $$$(3,1,4,2)$$$。对于 $$$n = 5$$$ — $$$(2,4,1,5,3)$$$, $$$(2,5,3,1,4)$$$, $$$(3,1,5,2,4)$$$, $$$(3,5,1,4,2)$$$, $$$(4,1,3,5,2)$$$, 和$$$(4,2,5,1,3)$$$。我们不会列出 $$$n = 9$$$ 的所有 28146,但例如 $$$(4,7,9,5,1,8,2,6,3)$$$、$$$(2,4,6,1,9,7,3,8,5)$$$、$$$(3,6,9,4,1,5,8,2,7)$$$ 和$$$(8,4,9,1,3,6,2,7,5)$$$ 是无区间的。
$$$n = 20$$$ 的确切值为 264111424634864638。