不知道为啥才30分

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define tul tuple<int,int,int>
#define all(x) x.begin(),x.end()
#define cy cout<<"Yes"<<endl
#define cn cout<<"No"<<endl 
#define lc rt<<1
#define rc rt<<1|1
const int N=3e6+6,yyx=10;
int n,m,k,a[N],p[N];
struct mat{
    int a,b;
    int arr[101][101];
    mat(int n,int m):a(n),b(m){
        memset(arr,0,sizeof arr);
    }
    mat operator* (const mat&w) const{
        mat res(a+1,w.b+1);
        for(int i=1;i<=a;++i){
            for(int j=1;j<=b;++j){
                for(int k=1;k<=w.b;++k){
                    res.arr[i][k]=(res.arr[i][k]+arr[i][j]*w.arr[j][k])%yyx;
                }
            }
        }
        return res;
    }
};
int mul(int x,int y){
    int res=1;
    while(y){
      if(y&1) res=(res*x)%yyx;
      x=(x*x)%yyx;
      y>>=1;
    }
    return res%yyx;
}
mat mqmi(mat x,int y){
    mat mt(2,3);
    for(int i=1;i<=2;++i) mt.arr[i][i]=1;
    while(y){
        if(y&1) mt=mt*x;
        x=x*x;
        y>>=1;
    }
    return mt;
}
inline void solve(){
  cin>>n>>m>>k;
  mat mt(2,3);
  mt.arr[1][2]=mt.arr[2][1]=mt.arr[1][1]=1;
  if(k<=(int)1e6){
    vector<int> a(k+1,0);
    a[1]=n,a[2]=m;
    for(int i=3;i<=k;++i){
        a[i]=a[i-1]*a[i-2]%yyx; 
    }
    cout<<a[k]<<endl;
    return;
  }
  mt=mqmi(mt,k-2);
  int ans=mul(n,mt.arr[2][1]+4)%yyx*mul(m,mt.arr[1][1]+4)%yyx;
  cout<<ans%yyx<<endl;
}
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  //freopen("D://321//in.txt","r",stdin);
  //freopen("D://321//out.txt","w",stdout);
  int _=1;
  //cin>>_;
  while(_--)
  solve();
  return 0;
}