{"raw_statement":[{"iden":"background","content":"翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) I 题。"},{"iden":"statement","content":"我们定义一个从 $1 \\sim n$ 的排列是“间隔排列”的情况是，在这个排列中存在连续的一段长度为 $2 \\sim n-1$ 的子区间使得这段子区间在排序后是一串连续的自然数。比如，$\\{6,7,1,8,5,3,2,4\\}$ 是一个“间隔排列”，因为 $\\{6,7\\}$，$\\{5,3,2,4\\}$，$\\{3,2\\}$ 经过排序后都是一段连续的自然数。\n\n现在已知 $n$，请你输出**不是**“间隔排列”的排列总数，由于输出可能很大，请对 $p$ 取模。"},{"iden":"input","content":"第一行两个整数 $t (1 \\leq t \\leq 400)$ 和 $p (10^8 \\leq p \\leq 10^9)$，分别表示数据组数和模数。\n\n接下来 $t$ 行，一行一个整数 $n (1 \\leq n \\leq 400)$。"},{"iden":"output","content":"对于每组数据输出 $1 \\sim n$ 的所有排列中**不是**“间隔排列”的排列总数对 $p$ 取模的值。"},{"iden":"note","content":"数据保证 $1 \\leq t \\leq 400$，$10^8 \\leq p \\leq 10^9$，$1 \\leq n \\leq 400$。\n\n对于样例一的解释：\n\n第二组数据存在 $\\{2,4,1,3\\}$ 和 $\\{3,1,4,2\\}$ 符合要求。\n\n第三组数据存在 $\\{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\n对于样例二，一共有 $264111424634864638$ 种可能。"}],"translated_statement":null,"sample_group":[["4 998244353\n1\n4\n5\n9","1\n2\n6\n28146"],["1 437122297\n20","67777575"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}