「LAOI-19」完美世界

题号：NC317389
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 一个世界可以用一个长度为 $n$ 的排列 $A$ 表示。每个人由两个不同的下标 $(x,y)\left(1\le x < y\le n\right)$ 表示。

$\hspace{15pt}$ 对于这个世界上任意两个人，我们分别用下标对 $(a,b)$ 和 $(c,d)$ 表示。由于神秘原因，两个人存在社会关系当且仅当 $a<b<c<d$ ，否则两人不存在社会关系。若两人存在社会关系，则其关系可能是以下三种之一：
$\hspace{23pt}\bullet\,$ 朋友： $|A_{a}-A_{d}|+|A_{b}-A_{c}|>|A_{a}-A_{c}|+|A_{b}-A_{d}|$ ；
$\hspace{23pt}\bullet\,$ 宿敌： $|A_{a}-A_{d}|+|A_{b}-A_{c}|<|A_{a}-A_{c}|+|A_{b}-A_{d}|$ ；
$\hspace{23pt}\bullet\,$ 路人。
$\hspace{15pt}$ 如果一个世界中同时存在至少一对“朋友”关系和至少一对“宿敌”关系，则称该世界是完美的。

$\hspace{15pt}$ 一共给出 $T$ 个世界，你需要对每一个世界分别求解，有多少种长度为 $n$ 的排列，使得该世界是完美的。由于世界很大，请将答案对给定的整数 $p$ 取模后输出。

【名词解释】
$\hspace{15pt}$ 长度为 $n$ 的排列：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

第一行输入两个正整数 ，表示世界数量、模数。
此后  行，第  行输入一个正整数 ，表示第  个世界的大小。

输出描述:

对于每一个世界，新起一行输出一个整数，表示有多少种长度为  的全排列，使得该世界是完美的。

示例1

输入

复制

6 998244353
5
6
7
80
90
100

输出

复制

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。