# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
55508849 |
Practice:
jdh |
1182E
- 28
|
C++17 (GCC 7-32)
|
Accepted
|
31 ms
|
144 KB
|
2019-06-12 23:02:41 |
2019-06-12 23:02:41 |
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N = 3;
const ll MOD = 1e9+7;
const ll MMOD = 1e9+6;
ll getPow(ll a,ll p){
ll ret = 1,cp = a;
while(p){
if(p&1) ret = (ret*cp)%MOD;
p >>= 1;
cp = (cp*cp)%MOD;
}
return ret;
}
ll getInverse(ll i){
return getPow(i,MOD-2)%MOD;
}
vector<vector<ll>> multi(vector<vector<ll>>& A,vector<vector<ll>>& B){
vector<vector<ll>> ret(N,vector<ll>(N));
for(int i = 0; i < N; ++i){
for(int j = 0; j < N; ++j){
for(int k = 0; k < N; ++k)
ret[i][j] = (ret[i][j]+A[i][k]*B[k][j])%MMOD;
}
}
return ret;
}
vector<vector<ll>> getMatrixPow(vector<vector<ll>>& A,ll K){
vector<vector<ll>> ret(N,vector<ll>(N));
for(int i = 0; i < N; ++i) ret[i][i] = 1;
while(K){
if(K&1) ret = multi(ret,A);
K >>= 1;
A = multi(A,A);
}
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll n,f1,f2,f3,c;
cin >> n >> f1 >> f2 >> f3 >> c;
if(f1 == 0 or f2 == 0 or f3 == 0 or c == 0){
cout << 0;
return 0;
}
vector<vector<ll>> M = { {1,1,1}, {1,0,0}, {0,1,0} };
vector<vector<ll>> M2 = getMatrixPow(M,n-3);
ll A = M2[0][0], B = M2[0][1], C = M2[0][2];
ll ans = 1,cp = 3*A+2*B+C-n;
if(cp > 0) ans = getPow(c,cp);
else{
ll c1 = getInverse(c);
ans = getPow(c1,-cp);
}
ans = (ans*getPow(f3,A))%MOD;
ans = (ans*getPow(f2,B))%MOD;
ans = (ans*getPow(f1,C))%MOD;
cout << (ans+MOD)%MOD;
return 0;
}
Click to see test details