记录编号	129210	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	清羽	是否通过	通过
代码语言	C++	运行时间	4.772 s
提交时间	2014-10-19 16:12:28	内存使用	0.32 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int SIZEN=2;

typedef long long LL;

LL t,MOD,n;

struct MATRAX{
	LL s[SIZEN][SIZEN];
	
	MATRAX operator *(const MATRAX& num){
		MATRAX c;
		for(int i=0;i<SIZEN;i++)
			for(int j=0;j<SIZEN;j++){
				c.s[i][j]=0;
				for(int k=0;k<SIZEN;k++) c.s[i][j]=(c.s[i][j]+s[i][k]*num.s[k][j]%MOD)%MOD;
			}
		return c;
	}
	
	MATRAX(LL a=0,LL b=0,LL c=0,LL d=0){
		s[0][0]=a,s[0][1]=b,s[1][0]=c,s[1][1]=d; 
	}
};

MATRAX I;

void init()
{
	I=MATRAX(1,1,1,0);
	scanf("%lld%lld",&n,&MOD);
}

void work()
{
	MATRAX c=MATRAX(1,0,0,1);
	while(n){
		if(n&1)  c=c*I;
		n>>=1;
		I=I*I;
	}
	printf("%lld\n",c.s[0][1]);
}

int main()
{
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	cin>>t;
	while(t--){
		init();
		work();
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}