E. Product Oriented Recurrence （矩阵快速幂新模板）

E. Product Oriented Recurrence

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let fx=c2x−6⋅fx−1⋅fx−2⋅fx−3fx=c2x−6⋅fx−1⋅fx−2⋅fx−3 for x≥4x≥4.

You have given integers nn, f1f1, f2f2, f3f3, and cc. Find fnmod(109+7)fnmod(109+7).

Input

The only line contains five integers nn, f1f1, f2f2, f3f3, and cc (4≤n≤10184≤n≤1018, 1≤f11≤f1, f2f2, f3f3, c≤109c≤109).

Output

Print fnmod(109+7)fnmod(109+7).

Examples

input

Copy

5 1 2 5 3

output

Copy

72900

input

Copy

17 97 41 37 11

output

Copy

317451037

Note

In the first example, f4=90f4=90, f5=72900f5=72900.

In the second example, f17≈2.28×1029587f17≈2.28×1029587.

仔细观察可以发现

其实f(n) 可以拆成 c^x1+f1^x2+f2^x3+f4^x4

我们只需要用递推式来求出x1 x2 x3 x4即可

代码

#include<bits/stdc++.h> using namespace std; const int maxn=5; const long long mod=1e9+6; const long long mod1=1e9+7; struct node {long long a[maxn][maxn]; }pos; node milt(node x,node y) {node res;memset(res.a,0,sizeof(res.a));for(int i=0;i<maxn;i++)for(int j=0;j<maxn;j++)for(int k=0;k<maxn;k++)res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%mod;return res; } node power(node mat,long long n) {node x,y;memset(x.a,0,sizeof(x.a));memset(y.a,0,sizeof(y.a));y=mat;for(int i=0;i<maxn;i++) x.a[i][i]=1;while(n!=0){if(n%2==1) x=milt(x,y);y=milt(y,y);n/=2;}return x; } long long quick_pow(long long a,long long b) {long long ans=1;a=a%mod1;while(b){if(b&1) ans=(ans*a)%mod1;b/=2;a=(a*a)%mod1;}return ans; } int main() {long long n,f1,f2,f3,c;long long cex,f1ex,f2ex,f3ex;cin>>n>>f1>>f2>>f3>>c;n-=3;node tmp;memset(tmp.a,0,sizeof(tmp.a));tmp.a[0][0]=1;tmp.a[0][1]=1;tmp.a[0][2]=1;tmp.a[0][3]=2;tmp.a[0][4]=-6;tmp.a[1][0]=1;tmp.a[2][1]=1;tmp.a[3][3]=1;tmp.a[3][4]=1;tmp.a[4][4]=1;node ans=power(tmp,n);cex=(ans.a[0][3]*4+ans.a[0][4])%mod;memset(tmp.a,0,sizeof(tmp.a));tmp.a[0][0]=1;tmp.a[0][1]=1;tmp.a[0][2]=1;tmp.a[1][0]=1;tmp.a[2][1]=1;ans=power(tmp,n);f1ex=(ans.a[0][2])%mod;f2ex=(ans.a[0][1])%mod;f3ex=(ans.a[0][0])%mod;long long ans1;long long num;// cout<<f1ex<<" "<<f2ex<<" "<<f3ex<<endl;ans1=quick_pow(c,cex)%mod1;ans1=ans1*quick_pow(f1,f1ex)%mod1;ans1=ans1*quick_pow(f2,f2ex)%mod1;ans1=ans1*quick_pow(f3,f3ex)%mod1;printf("%lld\n",ans1); }

 

总结

以上是生活随笔为你收集整理的E. Product Oriented Recurrence （矩阵快速幂新模板）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。