← 返回题目列表

Codeforces · 1089/I

I. 无区间排列

中文机器翻译题面 查看原题

考虑从 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。