1 //Accepted hdu1005 0MS 248K 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <queue> 6 #include <cmath> 7 #include <algorithm> 8 using namespace std; 9 /**10   * This is a documentation comment block11   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！12   * @authr songt13   */14 const int imax_n = 5;15 struct matrix16 {17     int n,m;18     int a[imax_n][imax_n];19     matrix mult(matrix x,int p)20     {21         matrix temp;22         if (m==x.n)23         {24             for (int i=1;i<=n;i++)25             {26                 for (int j=1;j<=x.m;j++)27                 {28                     temp.a[i][j]=0;29                     for (int k=1;k<=m;k++)30                     temp.a[i][j]=(temp.a[i][j]+a[i][k]%p*(x.a[k][j]%p)%p)%p;31                 }32             }33             temp.n=n;34             temp.m=x.m;35         }36         return temp;37     }38     /*39     matrix exp(int n,int p)40     {41         if (n!=m) return (*this);42         matrix temp=(*this);43         matrix res;44         res.n=res.m=n;45         for (int i=1;i<=n;i++)46         for (int j=1;j<=n;j++)47         res.a[i][j]=1;48         while (n)49         {50             if (n&1) res=res.mult(temp,p);51             temp=temp.mult(temp,p);52             n>>=1;53         }54         return res;55     }*/56     matrix exp(int n,int p)57     {58         matrix temp;59         if (n==1) return (*this);60         temp=exp(n/2,p);61         temp=temp.mult(temp,p);62         if (n%2==1) temp=temp.mult((*this),p);63         return temp;64     }65 };66 int a,b,n;67 void slove()68 {69     if (n==1 || n==2)70     {71         printf("1\n");72         return ;73     }74     matrix temp;75     temp.n=2;76     temp.m=2;77     temp.a[1][1]=a;78     temp.a[1][2]=1;79     temp.a[2][1]=b;80     temp.a[2][2]=0;81     temp=temp.exp(n-2,7);82     matrix ans;83     ans.n=1;84     ans.m=2;85     ans.a[1][1]=ans.a[1][2]=1;86     ans=ans.mult(temp,7);87     int res=ans.a[1][1];88     printf("%d\n",res);89 }90 int main()91 {92     while (scanf("%d%d%d",&a,&b,&n) && !(a==0 && b==0 && n==0))93     {94         slove();95     }96     return 0;97 }