//Accepted hdu1005 0MS 248K #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <cmath> #include <algorithm> using namespace std; /** * This is a documentation comment block * 如果有一天你坚持不下去了,就想想你为什么走到这儿! * @authr songt */ ; struct matrix { int n,m; int a[imax_n][imax_n]; matrix mult(matrix x,int p) { matrix temp; if (m==x.n) { ;i<=n;i++) { ;j<=x.m;j++) { temp.a[i][j]=; ;k<=m;k++) temp.a[i][j]=(temp.a[i][j]+a[i][k]%p*(x.a[k][j]%p)%p)%p; } } temp.n=n; temp.m=x.m; } return temp; } /* matrix exp(int n,int p) { if (n!=m) return (*this); matrix temp=(*this); matrix res; res.n=res.m=n; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) res.a[i][j]=1; while (n) { if (n&1) res=res.mult(temp,p); temp=temp.mult(temp,p); n>>=1; } return res; }*/ matrix exp(int n,int p) { matrix temp; ) return (*this); temp=exp(n/,p); temp=temp.mult(temp,p); ==) temp=temp.mult((*this),p); return temp; } }; int a,b,n; void slove() { || n==) { printf("1\n"); return ; } matrix temp; temp.n=; temp.m=; temp.a[][]=a; temp.a[][]=; temp.a[][]=b; temp.a[][]=; temp=temp.exp(n-,); matrix ans; ans.n=; ans.m=; ans.a[][]=ans.a[][]=; ans=ans.mult(temp,); ][]; printf("%d\n",res); } int main() { && b== && n==)) { slove(); } ; }