记录编号	60654	评测结果	AAAAAAAAAA
题目名称	选拔队员	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	Pascal	运行时间	0.143 s
提交时间	2013-05-28 16:49:00	内存使用	0.17 MiB

Program cog966;
    Type
        Mt=Array[1..2,1..2]Of Longint;
    Var
        A,S:Mt;
        T,N,M,I,J:Longint;
    Procedure Ms(A,B:Mt; Var S:Mt);
        Var
            I,J:Longint;
        Begin
            For I:=1 To 2 Do
                For J:=1 To 2 Do
                    S[I,J]:=(A[I,1]*B[1,J]+A[I,2]*B[2,J]) Mod M;
        End;
    Begin
        Assign(Input,'seata.in');
        Assign(Output,'seata.out');
        Reset(Input);
        Rewrite(Output);
        Readln(T,M);
        Repeat
            Dec(T);
            Readln(N);
            A[1,1]:=1;
            A[1,2]:=1;
            A[2,1]:=1;
            A[2,2]:=0;
            S[1,1]:=1;
            S[1,2]:=0;
            S[2,1]:=0;
            S[2,2]:=1;
            While N<>0 Do
                Begin
                    If N And 1=1 Then Ms(A,S,S);
                    Ms(A,A,A);
                    N:=N Shr 1;
                End;
            Writeln((S[1,1]+S[1,2]) Mod M);
        Until T=0;
        Close(Input);
        Close(Output);
    End.