Untitled

a guest
Jun 11th, 2019
550
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. #define mk make_pair
3. #define fs first
4. #define sc second
5. using namespace std;
6. typedef long long ll;
7. typedef long double ld;
8.
9. ll powmod(ll a, ll b, ll m)
10. {
11. ll res = 1;
12. while (b > 0)
13. {
14. if (b & 1)
15. {
16. res = (res * a) % m;
17. }
18. a = (a * a) % m;
19. b >>= 1;
20. }
21. return res;
22. }
23.
24. ll solve(ll a, ll b, ll m)
25. {
26. ll n = (ll) sqrt (m + .0) + 1;
27. map<ll, ll> vals;
28. for (ll p = n; p >= 1; --p)
29. vals[powmod(a, p * n, m)] = p;
30. for (ll q = 0; q <= n; ++q)
31. {
32. ll cur = (powmod(a, q, m) * b) % m;
33. if (vals.count(cur))
34. {
35. ll ans = vals[cur] * n - q;
36. assert(powmod(a,ans,m)==b);
37. return ans;
38. }
39. }
40. return -1;
41. }
42.
43.
44. #define Matrix vector< vector < long long > >
45. long long MOD=1000000007;
46. void Resize_Matrix(long long n, long long m, Matrix &M)
47. {
48. M.clear();
49. for(int j=0; j<n; j++)
50. {
51. M.push_back( vector< long long >() );
52. M[j].clear();
53. M[j].resize(m);
54. for(int i=0; i<m; i++)
55. M[j][i]=0;
56. }
57. }
58. Matrix Matrix_Multiplication(Matrix A, Matrix B)
59. {
60. Matrix Ans;
61. long long n, m;
62. Resize_Matrix(n=A.size(), m=A[0].size(), Ans);
63. for(long long j=0; j<n; j++)
64. {
65. for(long long i=0; i<m; i++)
66. {
67. Ans[j][i]=0;
68. for(long long k=0; k<m; k++)
69. {
70. Ans[j][i]+= A[j][k]*B[k][i];
71. Ans[j][i]%=MOD;
72. }
73. }
74. }
75. return Ans;
76. }
77. Matrix Matrix_Exponentiation(Matrix M, long long power)
78. {
79. if(power==1)
80. return M;
81. Matrix ret=Matrix_Exponentiation(M, power/2);
82. ret=Matrix_Multiplication(ret, ret);
83. if(power%2)
84. ret=Matrix_Multiplication(ret, M);
85. return ret;
86. }
87.
88. int main()
89. {
90. ll n, f1, f2, f3, c, x1, x2, x3;
91. while(cin>>n>>f1>>f2>>f3>>c)
92. {
93. ll ans=0;
94. x1 = solve(5, f1, MOD);
95. x2 = solve(5, f2, MOD);
96. x3 = solve(5, f3, MOD);
97. Matrix x;
98. Resize_Matrix(3, 3, x);
99. x[0][1]=1;
100. x[1][2]=1;
101. x[2][0]=x[2][1]=x[2][2]=1;
102. --MOD;
103. x=Matrix_Exponentiation(x, n-1);
104. ++MOD;
105. ans=x[0][0]*x1+x[0][1]*x2+x[0][2]*x3;
106. ans%=MOD-1;
107. ans=powmod(5, ans, MOD);
108. ll tmp;
109. n-=3;
110. if(n%2==0){
111. tmp=((n/2)%(MOD-1))*((n+1)%(MOD-1));
112. }
113. else{
114. tmp=((n)%(MOD-1))*(((n+1)/2)%(MOD-1));
115. }
116. n+=3;
117. tmp*=2;
118. tmp%=MOD-1;
119. tmp=powmod(c, tmp, MOD);
120. ans*=tmp;
121. ans%=MOD;
122. cout<<ans<<endl;
123. }
124. return 0;
125. }