背景

随着WZOI的老一辈人员的离开，WZOI的人数越来越少了。CJH教练于是想选拔一些人进入团队。。。。。。

问题描述

这一天，许多的学生齐聚在机房的门口，等待这CJH教练的出现。。。

CJH教练过了不久就来了，他看见那么多人来参加。虽然十分高兴，但是机房的位置十分有限，于是他要淘汰一部分人。

CJH教练说：“各位同学，十分高兴你们能来到这个机房。但是机房内的电脑的数目十分有限，现在如果你们能答出下面这个问题，那么你们就能成为团队的一份子。注意听，问题是这样子的：‘机房内总共有N（这个值CJH教练会告诉你）个位置，排列成一条直线，从左往右编号为1到N。现在你们中的N个人要坐到这N个位置上去，问总共有多少中安排的方法。”

所有同学大呼太难了，于是CJH教练决定简化问题：从同学中选出若干个男生和若干多个女生（即男女生的数目随便定）安排到机房内的N个位置上去，要求任意两位女生不能相邻（即任意两个女生之间必须有至少一个男生），问总共有多少种方法，你们姑且可以认为所有男生是等价的，所有女生是等价的。

CJH为了再次降低难度，他只要求你将方案种数mod M即可。

当然，由于这个问题简化之后太简单了，于是CJH会用不同的N提问多次，这样他就可以淘汰许多没能力的人了。

为了能顺利进入WZOI，许多同学向WZOI的朋友求救。显然你就是他们的救星了，现在将CJH教练的问题告诉你，要求你输出正确答案。

输入格式seat.in

输入数据第一行包含两个整数T，M，分别表示测试数据的组数和要将结果mod M；

接下来T行，每行有一个整数N，表示机房里总共有N个位置。

输出格式seat.out

输出数据共T行，每行一个整数S，表示总的方案数mod M之后的那个数。

样例输入输出

2 3
1
3

2
2

2 5
9
5

4
3

数据规模

对于10%的数据，N≤100，T≤10；

对于30%的数据，N≤1000，T≤100；

对于50%的数据，N≤1000000，T≤1000；

对于100%的数据，N≤1000000000，T≤10000；

对于100%的数据，M≤10。