记录编号	126091	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	Cirno	是否通过	通过
代码语言	C++	运行时间	3.829 s
提交时间	2014-10-10 22:48:59	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
using namespace std;
long long n,fn,p;
class squ
{
public:
	long long x1,x2,y1,y2;
};
squ operator *(squ a,squ b)
{
	squ ans;
	ans.x1=a.x1*b.x1+a.x2*b.y1,ans.x1%=p;
	ans.x2=a.x1*b.x2+a.x2*b.y2,ans.x2%=p;
	ans.y1=a.y1*b.x1+a.y2*b.y1,ans.y1%=p;
	ans.y2=a.y1*b.x2+a.y2*b.y2,ans.y2%=p;
	return ans;
}
squ POW(squ x,int y)
{
	if(y<=1)
		return x;
	if(y%2==0)
		return POW(x*x,y/2);
	return POW(x*x,y/2)*x;
}
void init()
{
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	squ b={1,0,0,0},f={1,1,1,0};
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>fn>>p;
		if(fn==0)
			cout<<0<<endl;
		else
		{
			cout<<((b*POW(f,fn-1)).x1)%p<<endl;
		}
	}
}
int main()
{
	init();
	return 0;
}