记录编号	75414	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	vector	是否通过	通过
代码语言	C++	运行时间	4.512 s
提交时间	2013-10-27 20:20:03	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int n,P;
 
struct Mat
{
	long long m[2][2];
	void Unit()
	{
		m[0][0]=m[1][1]=1;
		m[0][1]=m[1][0]=0;
	}
	void Init()
	{
		m[0][0]=0;
		m[1][1]=m[0][1]=m[1][0]=1;
	}
	Mat operator *(const Mat &x)const
	{
		Mat c,t=*this;
		for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
		{
			c.m[i][j]=0;
			for(int k=0;k<2;++k)
			c.m[i][j]=(c.m[i][j]+((t.m[i][k]*x.m[k][j])%P))%P;
		}
		return c;
	}
	
	Mat Pow(int x)
	{
		Mat r,t=*this;
		r.Unit();
		while(x)
		{
			if(x&1)r=r*t;
			t=t*t;
			x>>=1;
		}
		return r;
	}
}a;
 
int main()
{
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d",&n,&P);
		if(n==0)
		{
			puts("0");
			continue;
		}
		a.Init();
		a=a.Pow(n);
		printf("%d\n",a.m[0][1]);
	}
	return 0;
}