# 【題解】Codeforces 1228C. Primes and Multiplication

【Problem】https://codeforces.com/problemset/problem/1228/C
【Solution:】Exponentiating by Squaring (快速冪)

• pow_mod(a, b): standard implementaion of Binary Exponentiation
• See the illustration below.
```#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
const int MOD = 1e9+7;

ll pow_mod(ll a, ll b){
//快速冪 (a^b) % MOD
ll ret = 1;
ll now = a;
while (b) {
// b = 5 = b'101
// a^b = a^5 = a^4 * a^1
if (b & 1) {
// 需要這個冪次
ret *= now;
ret %= MOD;
}
now *= now; // a -> a^2 -> a^4 -> ...
now %= MOD; // avoid overflow
b >>= 1; // b 的二進位數字往右移一位元
}
return ret;
}

int main() {
int x; // 2≤𝑥≤10^9
ll n; // 1≤𝑛≤10^18
ll ans;
// Calculate 𝑓(𝑥,1)⋅𝑓(𝑥,2)⋅…⋅𝑓(𝑥,𝑛)mod(10^9+7).
// 𝑓(30,70)=𝑔(70,2)⋅𝑔(70,3)⋅𝑔(70,5)=2^1⋅3^0⋅5^1=10
while (cin >> x >> n){
ans = 1;
// search all 𝑝 in 𝑝𝑟𝑖𝑚𝑒(𝑥)
int sq = sqrt(x);
for (ll p=2; p<=sq; p++){
if (x % p != 0) continue;
while (x % p == 0) x /= p;

ll cnt = 0;
ll num = n;
while (num){
cnt += num / p;
num /= p;
}
ans *= pow_mod(p, cnt);
ans %= MOD;
}
if (x > 1){
ll p = x;
ll cnt = 0;
ll num = n;
while (num){
cnt += num / p;
num /= p;
}
ans *= pow_mod(p, cnt);
ans %= MOD;
}
cout << ans << '\n';
}
return 0;
}
```