记录编号	77811	评测结果	AAAAAAAAAA
题目名称	方程	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	Pascal	运行时间	0.003 s
提交时间	2013-11-02 18:23:09	内存使用	0.15 MiB

Program cog604;
    Type
        Bn=Array[0..160]Of Longint;
    Var
        G,X,K,I:Longint;
        A:Bn;
    Procedure Mul(Var A:Bn; B:Longint);
        Var
            I,J:Longint;
        Begin
            J:=0;
            For I:=1 To A[0] Do
                Begin
                    Inc(J,A[I]*B);
                    A[I]:=J Mod 10;
                    J:=J Div 10;
                End;
            While J>0 Do
                Begin
                    Inc(A[0]);
                    A[A[0]]:=J Mod 10;
                    J:=J Div 10;
                End;
        End;
    Procedure Dvd(Var A:Bn; B:Longint);
        Var
            I,J:Longint;
        Begin
            J:=0;
            For I:=A[0] Downto 1 Do
                Begin
                    J:=J*10+A[I];
                    A[I]:=J Div B;
                    J:=J Mod B;
                End;
            While (A[0]>1) And (A[A[0]]=0) Do Dec(A[0]);
        End;
    Begin
        Assign(Input,'equationz.in');
        Assign(Output,'equationz.out');
        Reset(Input);
        Rewrite(Output);
        Readln(K,X);
        G:=1;
        I:=X;
        X:=X Mod 1000;
        While I>0 Do
            Begin
                If I And 1=1 Then G:=G*X Mod 1000;
                X:=X*X Mod 1000;
                I:=I Shr 1;
            End;
        Dec(G);
        Dec(K);
        If K>G-K Then K:=G-K;
        A[0]:=1;
        A[1]:=1;
        For I:=G Downto G-K+1 Do Mul(A,I);
        For I:=K Downto 2 Do Dvd(A,I);
        For I:=A[0] Downto 1 Do Write(A[I]);
        Writeln;
        Close(Input);
        Close(Output);
    End.