题目描述

某一天，龙、仆、丝、玛四人聚在一块，商量着出一套 NOIP 模拟赛题，此时阿蕾奇诺突发奇想：要不要出一套只有「数据删除」的模拟赛？四人一拍即合，很快一致同意了这个决定。

小 Z 新学了 Ferrers 图像！他现在知道了一个图像是 Ferrers 图像当且仅当这个图像由若干行左对齐的方格责成，且从上到下每一行的方格个数单调不增。现在他定义了一个 Ferrers 图像是好的，当且仅当他与他关于主对角线（左上-右下对角线）转置相同，下图左侧为一个好的 Ferrers 图像，右侧不是好的 Ferrers 图像。

现在小 Z 给出了 $T$ 次询问，每次给出一个正整数 $n$，问有多少个好的 Ferrers 图像由 $n$ 个方框组成，由于答案可能很大，你只需要输出答案对 $p$（一个给定的数）取模之后的结果即可。

输入格式

第一行包含两个正整数 $T,p$，表示询问次数与模数。

接下来 $T$ 行，每行包含一个正整数 $n$，表示一次询问。

输出格式

对每次询问，输出一行一个整数，表示答案。

样例1输入

5 998244353
9
11
20
25
60

样例1输出

2
2
7
12
209

样例1解释

当 $n=11$ 时，共有以下两种好的 Ferrers 图像：

样例2输入

3 991145149
36
2995
199808

样例2输出

33
615985322
896418163

子任务

对所有数据，保证 $1\le T\le 2\times 10^5,1\le n\le 2\times 10^5,10^8\le p\le 10^9$。

本题存在子任务捆绑

​