1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long int64;
const int MAXA = 1e7 + 10;
const int AMXA = 1e7;
const int64 MOD = 1000000007;
int prime[MAXA], prime_cnt;
bool isntp[MAXA];
int64 phi[MAXA], sum_phi[MAXA];
void init_phi() {
phi[1] = 1;
for (int i = 2; i <= AMXA; i++) {
if (!isntp[i]) {
prime[++prime_cnt] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= prime_cnt && i * prime[j] <= AMXA; j++) {
isntp[i * prime[j]] = true;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
} else {
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
}
template <typename T>
T pow_mod(T a, T b, T MOD) {
T res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b /= 2;
}
return res;
}
int factors[50], fac_cnt;
int64 f(int64 n, int64 m, int facid) {
if (n == 1) {
return sum_phi[m];
}
if (m == 0) {
return 0;
}
return ((factors[facid] - 1) * f(n / factors[facid], m, facid - 1) % MOD +
f(n, m / factors[facid], facid) % MOD) %
MOD;
}
int64 get_pow(int64 k, int64 p) {
if (p == 1) {
return 1;
}
int64 tmp = pow_mod(k, get_pow(k, phi[p]), p);
return (tmp == 0) ? p : tmp;
}
int main() {
init_phi();
for (int i = 1; i <= AMXA; i++) {
sum_phi[i] = sum_phi[i - 1] + phi[i];
sum_phi[i] %= MOD;
}
int64 n, m, p;
while (cin >> n >> m >> p) {
fac_cnt = 0;
int64 tmp = n;
for (int i = 1; i <= prime_cnt; i++) {
if (!isntp[tmp]) {
factors[++fac_cnt] = tmp;
break;
} else {
if (tmp % prime[i] == 0) {
factors[++fac_cnt] = prime[i];
tmp /= prime[i];
}
}
}
int64 k = f(n, m, fac_cnt);
cout << get_pow(k, p) << endl;
}
}
|
