E. Product Oriented Recurrence(四个矩阵快速幂）

Let

You have given integers

Input

The only line contains five integers

Output

Print

Examples

Input

Copy

5 1 2 5 3

Output

Copy

Input

Copy

17 97 41 37 11

Output

Copy

317451037

Note

In the first example,

In the second example,

矩阵快速幂使用来加速加法的运算

而这个题目给的是乘法

所以要看看式子可不可与搞加法的样子

答案可以写成

ans = c的幂 * f1的幂 * f2的幂 * f3的幂

现在要全球的就是四个数的指数

显然是构造矩阵然后快速幂递推吧，然后就1e9+7是个质数

因此所有的指数都可以mod phi（1e9+7）

  1 #include"bits/stdc++.h"
  2 using namespace std;
  3 #define int long long
  4 const int N = 5;
  5 const int mod = 1e9+7;
  6 struct Mat
  7 {
  8     int a[6][6];
  9     Mat (){memset(a,0,sizeof a);}
 10 
 11 };
 12 
 13 inline Mat mul(Mat a,Mat b,int mod )
 14 {
 15     Mat c;
 16     for(int i=1;i<=N;i++)
 17     {
 18         for(int j=1;j<=N;j++)
 19         {
 20             for(int k=1;k<=N;k++)
 21             {
 22                 c.a[i][j] +=a. a[i][k]*b.a[k][j];
 23                 c.a[i][j] %= mod;
 24             }
 25 
 26 
 27         }
 28     }return c;
 29 }
 30 inline int ksm(int a,int b,int p)
 31 {
 32     int ans = 1; a%=p;
 33     for(;b;b>>=1,a*=a,a%=p)if(b&1)ans*=a,ans%=p;
 34     return ans;
 35 }
 36 int n,f1,f2,f3,c;
 37 
 38 signed main()
 39 {
 40     Mat base;
 41     base.a[1][1]=0;
 42     base.a[1][2]=0;
 43     base.a[1][3]=0;
 44     base.a[1][4]=1;
 45     base.a[1][5]=4;
 46 
 47     Mat t;
 48     t.a[1][1]=1; t.a[1][2]=1;
 49     t.a[2][1]=t.a[2][3]=1;
 50     t.a[3][1]=1;
 51     t.a[4][1]=-6; t.a[4][4]=t.a[4][5]=1;
 52     t.a[5][1]=2,t.a[5][5]=1;
 53 
 54     cin>>n; n-=3;
 55     cin>>f1>>f2>>f3>>c;
 56     Mat ans;
 57     for(int i=1;i<=5;i++)ans.a[i][i]=1;
 58     int b=n;
 59 
 60     b=n;
 61     for(;b;b>>=1,t=mul(t,t,1e9+6))if(b&1)ans=mul(ans,t,1e9+6);
 62     base=mul(base,ans,1e9+6);
 63     //cout<<base.a[1][1];
 64     int Ans = ksm(c,base.a[1][1],mod);
 65   //  cout<<Ans<<endl;
 66      memset(t.a,0,sizeof t.a);
 67     memset(base.a,0,sizeof base.a);
 68     memset(ans.a,0,sizeof ans.a);
 69 
 70 // f1
 71     for(int i=1;i<=5;i++)ans.a[i][i]=1;
 72     base.a[1][1]=0;
 73     base.a[1][2]=0;
 74     base.a[1][3]=1;
 75     t.a[1][1]=1; t.a[1][2]=1;
 76     t.a[2][1]=t.a[2][3]=1;
 77     t.a[3][1]=1;
 78     b=n;
 79     for(;b;b>>=1,t=mul(t,t,1e9+6))if(b&1)ans=mul(ans,t,1e9+6);
 80     base=mul(base,ans,1e9+6);
 81     Ans *= ksm(f1,base.a[1][1],mod); Ans %= mod;
 82  //   cout<<base.a[1][1]<<endl;
 83     memset(t.a,0,sizeof t.a);
 84     memset(base.a,0,sizeof base.a);
 85      memset(ans.a,0,sizeof ans.a);
 86 
 87 
 88 //f2
 89     for(int i=1;i<=5;i++)ans.a[i][i]=1;
 90     base.a[1][1]=0;
 91     base.a[1][2]=1;
 92     base.a[1][3]=0;
 93     t.a[1][1]=1; t.a[1][2]=1;
 94     t.a[2][1]=t.a[2][3]=1;
 95     t.a[3][1]=1;
 96     b=n;
 97     for(;b;b>>=1,t=mul(t,t,1e9+6))if(b&1)ans=mul(ans,t,1e9+6);
 98     base=mul(base,ans,1e9+6);
 99     Ans *= ksm(f2,base.a[1][1],mod); Ans %= mod;
100    //     cout<<base.a[1][1]<<endl;
101 
102     memset(t.a,0,sizeof t.a);
103     memset(base.a,0,sizeof base.a);
104      memset(ans.a,0,sizeof ans.a);
105 
106 // f3
107 
108     for(int i=1;i<=5;i++)ans.a[i][i]=1;
109     base.a[1][1]=1;
110     base.a[1][2]=0;
111     base.a[1][3]=0;
112     t.a[1][1]=1; t.a[1][2]=1;
113     t.a[2][1]=t.a[2][3]=1;
114     t.a[3][1]=1;
115     b=n;
116     for(;b;b>>=1,t=mul(t,t,1e9+6))if(b&1)ans=mul(ans,t,1e9+6);
117     base=mul(base,ans,1e9+6);
118     Ans *= ksm(f3,base.a[1][1],mod); Ans %= mod;
119     //    cout<<base.a[1][1]<<endl;
120 
121 
122     cout<<Ans;
123 
124 
125 
126 
127 
128 
129 
130 
131 
132 }