记录编号	121757	评测结果	AAAAAAAAAA
题目名称	选拔队员	最终得分	100
用户昵称	JSX	是否通过	通过
代码语言	C++	运行时间	0.120 s
提交时间	2014-09-21 11:49:36	内存使用	0.29 MiB

#include<cstdio>
using namespace std;

int T,Mod;

struct Matrix{
	int ele[2][2];
	
	Matrix operator * (const Matrix& b)
	{
		Matrix c={0};
		
		for(int i=0;i<2;++i)
		{
			for(int j=0;j<2;++j)
			{
				for(int k=0;k<2;++k)
				{
					c.ele[i][j]=(c.ele[i][j]+ele[i][k]*b.ele[k][j]%Mod)%Mod;
				}
			}
		}
		
		return c;
	}
	
	Matrix operator *= (const Matrix& b){
		*this=*this*b;
	}
	
}A,B;

void QuickPow(long long N)
{	
	while(N>0)
	{
		if(N&1){
			B*=A;
		}
		A*=A;	N>>=1; 
	}
}

void Push_A(void)//初始矩阵 
{
	A.ele[0][0] = 1; A.ele[0][1] = 1;
    A.ele[1][0] = 1; A.ele[1][1] = 0;
}

void Push_B(void) 
{
	B.ele[0][0] = 1; B.ele[0][1] = 0; 
    B.ele[1][0] = 0; B.ele[1][1] = 1; 
}

int main()
{
	
	freopen("seata.in","r",stdin);
	freopen("seata.out","w",stdout);
	
	scanf("%d%d",&T,&Mod);
	
	long long N;
	for(int i=1;i<=T;++i)
	{
		scanf("%lld",&N);
		
		Push_A(); Push_B();
		
		QuickPow(N);
		
		printf("%d\n",(B.ele[0][0]+B.ele[0][1])%Mod);
	}
	
	
	return 0;
}