P9799 [NERC 2018] Interval-Free Permutations

翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) 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$ 取模的值。

数据保证 $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$ 种可能。