CSES Problem Set — Exponentiation II 題解
===

題目
---
你的任務是有效率地算出 $a^{b^c}$ 模 $10^9+7$ 的值。

注意到在這題我們令 $0^0 = 1$。

### 輸入
- 第一行輸入一個整數 $n$，代表計算的個數。（$1 \le n \le 10^5$）
- 接著有 $n$ 行，每一行有三個整數 $a$、$b$、$c$。（$0 \le a,b,c \le 10^9$）

### 輸出
輸出 $a^{b^c}$ 模 $10^9+7$ 的值。

範例測資
---

Input :
3
3 7 1
15 2 2
3 4 5

Output :
2187
50625
763327764

想法：快速冪配費馬小定理
---
這題跟上一題 Exponentiation 一樣可以使用快速冪解答。不過我們會發現到指數的部分是 $b^c$，一樣可能會超出整數上限所以不能算出實際數值。問題有點棘手，不過還好 $10^9+7$ 是個質數，代表我們可以利用數論的「費馬小定理」：

> 如果 $p$ 是質數，則對於任何與 $p$ 互質的整數 $a$ 都有 $a^{p-1} \equiv 1 \pmod{p}$。

這也就是說在算 $a$ 的次方時，多乘上 $p-1$ 次的 $a$ 在對 $p$ 取模的意義下其實相當於沒有乘（不論 $a$ 是否與 $p$ 互質都是如此），於是我們要算的值就變成了：\\[
a^{\displaystyle(b^c \bmod (p-1))} \bmod p.
\\] 其中 $p$ 是質數 $10^9+7$。

因為快速冪有不少種寫法，下面的範例程式碼省略不定義 `fastpow`，詳細的寫法參考上一題 Exponentiation。

### 範例程式碼

#include <iostream>
using namespace std;

int MOD = 1000000007;
int fastpow(int x, int n, int mod);

int main() {
    int n, a, b, c;
    cin >> n;
    for (int i = 0; i < n; i++) {
      cin >> a >> b >> c;
      cout << fastpow(a, fastpow(b, c, MOD-1), MOD);
    }    
}