Codeforces Round #566 (Div. 2) 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

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 .

很明显要求c的指数 f1的指数 f2的指数 f3的指数

设c 的指数为 An

那么易得 An= An-1 +An-2 +An-3 +2*n-6

然后构造矩阵

1 1 0 0 0

1 0 1 0 0

1 0 0 0 0

1 0 0 1 0

1 0 0 -1/3 1

-1/3要取在mod 欧拉(1e9+7)条件下的逆元

A的初始矩阵 0 0 0 8 -6

在矩阵快速幂过程中

mod取欧拉（1e9+7）

对于f的系数有 Fn=Fn+Fn-2+Fn-3

因为有3个（f1,f2,f3）初始项矩阵不同但是递推式一样

F的构造矩阵为

1 1 0

1 0 1

1 0 0

f1初始矩阵 0 0 1

f2初始矩阵 0 1 0

f3初始矩阵 1 0 0

注意欧拉降幂

直接矩阵快速幂

完后ans=c的多少次方*f1的多少次方*f2的多少次方*f3的多少次方

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
typedef long long ll;
long long mod=1e9+7;
long long qpow(long long a,long long n)
{
    long long ans=1;
    long long base=a;
    while(n)
    {
        if(n&1)
            ans=ans*base%mod;
        base=base*base%mod;
        n>>=1;
    }
    return ans;
}
long long ol(long long x)
{
	long long i,res=x;
	for(i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			res=res-res/i;
			while(x%i==0)
				x/=i;
		}
	}
	if(x>1)
		res=res-res/x;
	return res;
}
int N=5;
struct Matrix{///矩阵结构体
    ll matrix[5][5];
};
Matrix a,b;
void init(Matrix &res)///初始化为单位矩阵
{
    memset(res.matrix,0,sizeof(res.matrix));
    for(int i=0;i<N;i++)
        res.matrix[i][i]=1;
}
Matrix multiplicative(Matrix a,Matrix b)///矩阵乘法
{
    Matrix res;
    memset(res.matrix,0,sizeof(res.matrix));
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            for(int k = 0 ; k < N ; k++){
                res.matrix[i][j] += a.matrix[i][k]*b.matrix[k][j];
                res.matrix[i][j]+=mod;
                res.matrix[i][j] %= mod;
            }
        }
    }
    return res;
}
Matrix Pow(Matrix mx,ll m)///矩阵快速幂
{
    Matrix res,base=mx;
    init(res);
    while(m)
    {
        if(m&1)
            res=multiplicative(res,base);
        base=multiplicative(base,base);
        m>>=1;
    }
    return res;
}
long long n,f1,f2,f3,c;
Matrix ATP,ADP,TCP,UDP;
int main()
{
    //printf("%lld",ol(mod-1));
    scanf("%lld%lld%lld%lld%lld",&n,&f1,&f2,&f3,&c);
    memset(a.matrix,0,sizeof(a.matrix));
    memset(b.matrix,0,sizeof(b.matrix));
    mod-=1;
    a.matrix[0][0]=1;
    a.matrix[0][1]=1;
    a.matrix[0][2]=1;
    a.matrix[0][3]=1;
    a.matrix[0][4]=1;
    a.matrix[1][0]=1;
    a.matrix[2][1]=1;
    a.matrix[3][3]=1;
    a.matrix[3][4]=(-qpow(3,(ol(mod)-1+mod)%mod)+mod)%mod;
    a.matrix[4][4]=1;
    b.matrix[0][0]=1;
    b.matrix[0][1]=1;
    b.matrix[0][2]=1;
    b.matrix[1][0]=1;
    b.matrix[2][1]=1;
    //ATP.matrix[0][0]=0;
    //ATP.matrix[1][0]=f2;
    //ATP.matrix[2][0]=f1;
    ATP.matrix[3][0]=8;
    ATP.matrix[4][0]=(-6+mod)%mod;

    Matrix op=Pow(a,n-3);
    Matrix ty=multiplicative(op,ATP);
    ll you=ty.matrix[0][0];
    //printf("%lld\n",you);
    N=3;
    ll ans=1;
    mod++;
    ans=ans*qpow(c,you)%mod;
    mod--;
    ADP.matrix[2][0]=1;
    TCP.matrix[1][0]=1;
    UDP.matrix[0][0]=1;
    Matrix tp=Pow(b,n-3);
    Matrix p1=multiplicative(tp,ADP);
    Matrix p2=multiplicative(tp,TCP);
    Matrix p3=multiplicative(tp,UDP);
    mod++;
    //printf("%lld  %lld  %lld  %lld\n",you,p1.matrix[0][0],p2.matrix[0][0],p3.matrix[0][0]);
    ans=ans*qpow(f1,p1.matrix[0][0])%mod;
    ans=ans*qpow(f2,p2.matrix[0][0])%mod;
    ans=ans*qpow(f3,p3.matrix[0][0])%mod;
    printf("%lld\n",ans);

}