记录编号	75492	评测结果	WWWWAWAWWW
题目名称	eins	最终得分	20
用户昵称	钨铅	是否通过	未通过
代码语言	Pascal	运行时间	3.612 s
提交时间	2013-10-27 23:56:29	内存使用	0.15 MiB

program eins;
type matrix=array[1..2,1..2]of longint;
var a,c:matrix;
    b,ans:array[1..2]of longint;
    i,j,n,mo,t,q:longint;
function mul(a,b:matrix;n,r,m:longint):matrix;
var c:matrix;
    i,j,k:longint;
begin
fillchar(c,sizeof(c),0);
for i:=1 to n do
 for j:=1 to m do
  for k:=1 to r do c[i,j]:=(c[i,j]+a[i,k]*b[k,j]) mod mo;
mul:=c;
end;
function mpower(a:matrix;n,r,m,x:longint):matrix;
var c:matrix;
begin
if x=1 then mpower:=a else begin
                           c:=mpower(a,n,r,m,x shr 1);
                           c:=mul(c,c,n,r,m);
                           if odd(x) then mpower:=mul(c,a,n,r,m)
                                     else mpower:=c;
                           end;
end;
begin
assign(input,'eins.in');
assign(output,'eins.out');
reset(input);
rewrite(output);
read(t);
for q:=1 to t do begin
a[1,1]:=0;
a[1,2]:=1;
a[2,1]:=1;
a[2,2]:=1;
b[1]:=1;
b[2]:=1;
fillchar(ans,sizeof(ans),0);
fillchar(c,sizeof(c),0);
read(n,mo);
if n=1 then begin
            writeln('1');
            continue;
            end;
c:=mpower(a,2,2,2,n-1);
for i:=1 to 2 do
 for j:=1 to 2 do ans[i]:=(ans[i]+b[j]*c[j,i]) mod mo;
writeln(ans[1]);
end;
close(input);
close(output);
end.