Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define mk make_pair
- #define fs first
- #define sc second
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- ll powmod(ll a, ll b, ll m)
- {
- ll res = 1;
- while (b > 0)
- {
- if (b & 1)
- {
- res = (res * a) % m;
- }
- a = (a * a) % m;
- b >>= 1;
- }
- return res;
- }
- ll solve(ll a, ll b, ll m)
- {
- ll n = (ll) sqrt (m + .0) + 1;
- map<ll, ll> vals;
- for (ll p = n; p >= 1; --p)
- vals[powmod(a, p * n, m)] = p;
- for (ll q = 0; q <= n; ++q)
- {
- ll cur = (powmod(a, q, m) * b) % m;
- if (vals.count(cur))
- {
- ll ans = vals[cur] * n - q;
- assert(powmod(a,ans,m)==b);
- return ans;
- }
- }
- return -1;
- }
- #define Matrix vector< vector < long long > >
- long long MOD=1000000007;
- void Resize_Matrix(long long n, long long m, Matrix &M)
- {
- M.clear();
- for(int j=0; j<n; j++)
- {
- M.push_back( vector< long long >() );
- M[j].clear();
- M[j].resize(m);
- for(int i=0; i<m; i++)
- M[j][i]=0;
- }
- }
- Matrix Matrix_Multiplication(Matrix A, Matrix B)
- {
- Matrix Ans;
- long long n, m;
- Resize_Matrix(n=A.size(), m=A[0].size(), Ans);
- for(long long j=0; j<n; j++)
- {
- for(long long i=0; i<m; i++)
- {
- Ans[j][i]=0;
- for(long long k=0; k<m; k++)
- {
- Ans[j][i]+= A[j][k]*B[k][i];
- Ans[j][i]%=MOD;
- }
- }
- }
- return Ans;
- }
- Matrix Matrix_Exponentiation(Matrix M, long long power)
- {
- if(power==1)
- return M;
- Matrix ret=Matrix_Exponentiation(M, power/2);
- ret=Matrix_Multiplication(ret, ret);
- if(power%2)
- ret=Matrix_Multiplication(ret, M);
- return ret;
- }
- int main()
- {
- ll n, f1, f2, f3, c, x1, x2, x3;
- while(cin>>n>>f1>>f2>>f3>>c)
- {
- ll ans=0;
- x1 = solve(5, f1, MOD);
- x2 = solve(5, f2, MOD);
- x3 = solve(5, f3, MOD);
- Matrix x;
- Resize_Matrix(3, 3, x);
- x[0][1]=1;
- x[1][2]=1;
- x[2][0]=x[2][1]=x[2][2]=1;
- --MOD;
- x=Matrix_Exponentiation(x, n-1);
- ++MOD;
- ans=x[0][0]*x1+x[0][1]*x2+x[0][2]*x3;
- ans%=MOD-1;
- ans=powmod(5, ans, MOD);
- ll tmp;
- n-=3;
- if(n%2==0){
- tmp=((n/2)%(MOD-1))*((n+1)%(MOD-1));
- }
- else{
- tmp=((n)%(MOD-1))*(((n+1)/2)%(MOD-1));
- }
- n+=3;
- tmp*=2;
- tmp%=MOD-1;
- tmp=powmod(c, tmp, MOD);
- ans*=tmp;
- ans%=MOD;
- cout<<ans<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement