cf 1182E Product Oriented Recurrence（欧拉定理 + 矩阵快速幂

description

Let $f_x=c^{2x-6}\cdot f_{x-1}\cdot f_{x-2}\cdot f_{x-3}$fx​=c2x−6⋅fx−1​⋅fx−2​⋅fx−3​ for $x\ge 4$x≥4
You have given integers $n$n, $f_1$f1​, $f_2$f2​, $f_3$f3​, and $c$c. Find $f_{n}mod(10^9+7)$fn​ mod (109+7).

Input

The only line contains five integers $n$n, $f_1$f1​, $f_2$f2​, $f_3$f3​, and $c$c ( $4\le n\le 10^{18},1\le f_1,f_2,f_3,c\le 10^9$4≤n≤1018,1≤f1​,f2​,f3​,c≤109).

Output

Print $f_{n}mod(10^9+7)$fn​ mod (109+7).

Examples

Input

5 1 2 5 3

Output

72900

Input

17 97 41 37 11

Output

317451037

分析

对原式子两边取对数，有
$ln{f}_x=(2x-6)\cdot lnc+ln{f}_{x-1}+ln{f}_{x-2}+ln{f}_{x-3}$lnfx​=(2x−6)⋅lnc+lnfx−1​+lnfx−2​+lnfx−3​
可以构造出矩阵，即
(lnfn​​lnfn−1​​lnfn−2​​(2n−4)lnc​lnc​)=(lnfn−1​​lnfn−2​​lnfn−3​​(2n−6)lnc​lnc​)⎝⎜⎜⎜⎜⎛​11110​10000​01000​00012​00001​⎠⎟⎟⎟⎟⎞​
矩阵快速幂即可。
注意矩阵快速幂取模的时候是对 $\phi (1e9+7)$φ(1e9+7) 即 $1e9+6$1e9+6 取模(欧拉定理

代码如下

#include <bits/stdc++.h>
#define LL long long
#define mem(p) memset(&p, 0, sizeof(p))
using namespace std;
const int mod = 1e9 + 7;
const int modd = 1e9 + 6;
struct mat{
	LL a[5][5], r, c;
};
LL n, f1, f2, f3, c;
mat mul(mat x, mat y){
	mat p;
	mem(p);
	LL i, j, k;
	for(i = 0; i < x.r; i++){
		for(j = 0; j < y.c; j++){
			for(k = 0; k < x.c; k++)
				p.a[i][j] = (p.a[i][j] + x.a[i][k] * y.a[k][j] % modd) % modd;
		}
	}
	p.r = x.r;
	p.c = y.c;
	return p;
}
LL KSM(LL a, LL b, LL p){
	LL s = 1;
	while(b){
		if(b % 2) s = s * a % mod;
		a = a * a % mod;
		b /= 2;
	}
	return s;
}
LL ksm(LL b){
	mat ans, p;
	mem(ans);
	mem(p);
	p.a[0][0] = p.a[1][0] = p.a[2][0] = p.a[3][0] = p.a[0][1] = p.a[1][2] = p.a[3][3]
	= p.a[4][4] = 1;
	p.a[4][3] = 2;
	p.c = p.r = 5;
	ans = p;
	while(b > 0ll){
		if(b % 2) ans = mul(ans, p);
		p = mul(p, p);
		b /= 2;
	}
	//printf("%lld %lld %lld %lld\n", ans.a[3][0] * 2 + ans.a[4][0], ans.a[2][0], ans.a[1][0], ans.a[0][0]);
	return KSM(c, (ans.a[3][0] * 2 % modd + ans.a[4][0]) % modd, mod) * KSM(f1, ans.a[2][0], mod) % mod * KSM(f2, ans.a[1][0], mod) % mod * KSM(f3, ans.a[0][0], mod) % mod;
}
int main(){
	int i, j, m;
	scanf("%lld%lld%lld%lld%lld", &n, &f1, &f2, &f3, &c);
	printf("%lld", (ksm(n - 4) % mod + mod) % mod);
	return 0;
}