记录编号	321308	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	NVIDIA	是否通过	通过
代码语言	C++	运行时间	2.066 s
提交时间	2016-10-13 17:34:54	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
using namespace std;
long long n,fn,p;
struct XTT
{
	long long x1,x2,y1,y2;
};
XTT operator *(XTT a,XTT b)
{
	XTT 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;
}
XTT POW(XTT 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;
}
int main()
{
	
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	XTT b={1,0,0,0}; 
	XTT f={1,1,1,0};
	cin>>n;
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&fn,&p);
		if(fn==0)
			cout<<0<<endl;
		else
		{
			printf("%d\n",((b*POW(f,fn-1)).x1)%p);
		}
	}
	return 0;
}