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

每个排列都有一些平凡区间——即整个排列本身以及每一个单独的元素。如果一个排列不包含非平凡区间，我们称该排列为“无区间排列”（interval-free）。换句话说，无区间排列不包含长度在 $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$)，表示排列的长度。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示无区间排列的数量对 $p$ 取模的结果。

样例

输入 1

4 998244353
1
4
5
9

输出 1

1
2
6
28146

输入 2

1 437122297
20

输出 2

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$。