记录编号	72646	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2013]矩阵游戏	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	Pascal	运行时间	5.724 s
提交时间	2013-10-18 18:46:32	内存使用	7.79 MiB

Program cog1397;
    Const
        Moder=1000000007;
    Type
        Matrix=Array[1..2]Of Int64;
    Var
        N,M:Array[1..1000010]Of Longint;
        Mm,Mn:Matrix;
        A,B,C,D,Nl,Ml:Longint;
    Procedure Readin(Var A:Array Of Longint; Var L:Longint);
        Var
            C:Char;
            I:Longint;
        Begin
            L:=0;
            Read(C);
            Repeat
                Inc(L);
                A[L]:=Ord(C)-48;
                Read(C);
            Until C=' ';
            Dec(A[L]);
            For I:=L Downto 1 Do
                If A[I]<0
                    Then Begin
                             Inc(A[I],10);
                             Dec(A[I-1]);
                         End
                    Else Break;
        End;
    Function Matrixmul(A,B:Matrix):Matrix; Inline;
        Var
            S:Matrix;
        Begin
            S[1]:=A[1]*B[1] Mod Moder;
            S[2]:=(A[1]*B[2]+A[2]) Mod Moder;
            Exit(S);
        End;
    Function Matrixexp(A:Matrix; L:Longint; Var B:Array Of Longint):Matrix;
        Var
            S,T:Matrix;
            I:Longint;
        Begin
            S[1]:=1;
            S[2]:=0;
            While L<>0 Do
                Begin
                    T:=Matrixmul(A,A);
                    I:=B[L];
                    While I<>0 Do
                        Begin
                            If I And 1=1 Then S:=Matrixmul(S,A);
                            A:=Matrixmul(A,A);
                            I:=I Shr 1;
                        End;
                    A:=Matrixmul(T,T);
                    A:=Matrixmul(A,A);
                    A:=Matrixmul(A,T);
                    Dec(L);
                End;
            Exit(S);
        End;
    Begin
        Assign(Input,'matrixb.in');
        Assign(Output,'matrixb.out');
        Reset(Input);
        Rewrite(Output);
        Readin(N,Nl);
        Readin(M,Ml);
        Readln(A,B,C,D);
        Mm[1]:=A;
        Mm[2]:=B;
        Mn[1]:=C;
        Mn[2]:=D;
        Mm:=Matrixexp(Mm,Ml,M);
        Mn:=Matrixmul(Mm,Mn);
        Mn:=Matrixexp(Mn,Nl,N);
        Mn:=Matrixmul(Mn,Mm);
        Writeln((Mn[1]+Mn[2]) Mod Moder);
        Close(Input);
        Close(Output);
    End.