题目背景

翻译自 NERC 2018 I 题。

题目描述

我们定义一个从 $1 \sim n$ 的排列是“间隔排列”的情况是，在这个排列中存在连续的一段长度为 $2 \sim n-1$ 的子区间使得这段子区间在排序后是一串连续的自然数。比如，$\{6,7,1,8,5,3,2,4\}$ 是一个“间隔排列”，因为 $\{6,7\}$，$\{5,3,2,4\}$，$\{3,2\}$ 经过排序后都是一段连续的自然数。

现在已知 $n$，请你输出不是“间隔排列”的排列总数，由于输出可能很大，请对 $p$ 取模。

输入格式

第一行两个整数 $t (1 \leq t \leq 400)$ 和 $p (10^8 \leq p \leq 10^9)$，分别表示数据组数和模数。

接下来 $t$ 行，一行一个整数 $n (1 \leq n \leq 400)$。

输出格式

对于每组数据输出 $1 \sim n$ 的所有排列中不是“间隔排列”的排列总数对 $p$ 取模的值。

4 998244353
1
4
5
9

1
2
6
28146

1 437122297
20

67777575

提示

数据保证 $1 \leq t \leq 400$，$10^8 \leq p \leq 10^9$，$1 \leq n \leq 400$。

对于样例一的解释：

第二组数据存在 $\{2,4,1,3\}$ 和 $\{3,1,4,2\}$ 符合要求。

第三组数据存在 $\{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\}$ 满足要求。

对于样例二，一共有 $264111424634864638$ 种可能。