codefroces 1182E

1182 E. Product Oriented Recurrence

. .

. .

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
using namespace std;
const int N=1e6;
const long long mod=1e9+7;
const long long M=1e9+6;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
ll C[]={14,6,2,7,1};
ll f[4][3]={0,0,0,2,1,1,3,2,1,4,2,1};
auto md=[](ll num){
    return (num%M+M)%M;
};
struct mat{
    ll m[5][5];
    mat(){me(m,0);}
}F[2];
mat mulmat(mat a,mat b,int n){
    mat t;mat();
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                t.m[i][j]+=a.m[i][k]*b.m[k][j];
                t.m[i][j]=md(t.m[i][j]);
            }
        }
    }
    return t;
}
mat km(mat a,ll b,int n){
    mat ans;mat();
    for(int i=0;i<n;i++)ans.m[i][i]=1;
    for(;b;b>>=1,a=mulmat(a,a,n))if(b&1)ans=mulmat(ans,a,n);
    return ans;
}
void pre(){
    mat();
    F[0].m[0][0]=F[0].m[0][1]=F[0].m[0][2]=1;F[0].m[0][3]=2,F[0].m[0][4]=-6;
    F[0].m[1][0]=F[0].m[2][1]=F[0].m[3][3]=F[0].m[3][4]=F[0].m[4][4]=1;
    F[1].m[0][0]=F[1].m[0][1]=F[1].m[0][2]=F[1].m[1][0]=F[1].m[2][1]=1;
}
ll n,f1,f2,f3,c;
int main(){
    //freopen("in.txt","r",stdin);
    pre();
    cin>>n>>f1>>f2>>f3>>c;    
    auto cal=[](ll x,ll y,ll z,ll w){
        return ksm(c,x,mod)*ksm(f1,y,mod)%mod*ksm(f2,z,mod)%mod*ksm(f3,w,mod)%mod;
    };
    if(n==4)return o(cal(2,1,1,1));
    if(n==5)return o(cal(6,1,2,2));
    if(n==6)return o(cal(14,2,3,4));
    F[0]=km(F[0],n-6,5);
    F[1]=km(F[1],n-6,3);
    ll x=0,y=0,z=0,w=0;
    for(int i=0;i<5;i++){
        x+=F[0].m[0][i]*C[i];
        x=md(x);
    }
    for(int i=0;i<3;i++){
        y+=F[1].m[0][i]*f[1][i];
        z+=F[1].m[0][i]*f[2][i];
        w+=F[1].m[0][i]*f[3][i];
        y=md(y),z=md(z),w=md(w);
    }
    return o(cal(x,y,z,w));
}