记录编号	113866	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	1.260 s
提交时间	2014-07-26 15:12:11	内存使用	0.26 MiB

#include <cstdio>
#include <cstring>

int t,n;
unsigned long long p;

struct matrix
{
	unsigned long long a,b,c,d;
	matrix& operator=(const matrix &B)
	{a=B.a; b=B.b; c=B.c; d=B.d; return *this;}
	matrix operator*(const matrix &B)const
	{
		return (matrix){(a*B.a+b*B.c)%p,
			(a*B.b+b*B.d)%p,
			(c*B.a+d*B.c)%p,
			(c*B.b+d*B.d)%p};
	}
}E,F,T;

matrix pow(matrix A,int k)
{
	matrix R=E;
	while (k)
	{
		if (k&1) R=R*A;
		A=A*A; k>>=1;
	}
	return R;
}

int main()
{
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	E=(matrix){1,0,0,1};
	F=(matrix){1,1,1,0};
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d%lld",&n,&p);
		if (n==0) {printf("0\n"); continue;}
		T=pow(F,n-1);
		printf("%lld\n",T.a%p);
	}
	fclose(stdin); fclose(stdout);
	return 0;
}