U177075 [JDWOI-2] 括号串

括号，在一张一合中尽显美感。

小 M 写下了一个长度为 $n$ 的括号串，使得其中能够成功匹配的括号对数尽可能多。 但第二天，小 M 却找不到她的括号串了，于是她去找小 K 帮忙，并仅仅告诉他括号串的长度。小 K 清楚的知道，这样的括号串有很多个，所以他问你，一共有多少个括号串满足要求呢？由于答案很大，他只需知道答案对 $M$ 取模后的结果。

**本题多测**。 第一行两个整数 $Q,M$，表示数据组数和模数，保证 $M$ 是质数。 对于每组数据，一行一个整数 $n$，表示括号串长度。

对于每组数据，一行一个整数，表示答案对 $M$ 取模后的值。

**【样例解释】** 当 $n=1$ 时，满足要求的括号串为 ```(``` 和 ```)```。 当 $n=2$ 时，满足要求的括号串为 ```()```。 当 $n=3$ 时，满足要求的括号串为 ```(()``` , ```()(```，```)()```，```())```。 **【数据范围】** 对于 $10\%$ 的数据，$1\leq n\leq 20$； 对于 $40\%$ 的数据，$1\leq n\leq 2\times10^3$； 对于 $100\%$ 的数据，$1\leq n\leq 2\times10^6$，$1\leq Q\leq 2\times10^5$，$10^7\leq M\leq 2\times10^9$。