<style>
html, body, .ui-content {
background-image: url(https://truth.bahamut.com.tw/s01/201508/7f0e4bd0e01135c9df434733e0d1544a.JPG);
background-color: #333;
color: #DDD;
}
</style>

###### tags: `Meowmeow Online Judge`

# Exponentiation II
## Description

Your task is to efficiently values $a^{b^c}$ modulo $10^9+7$. Note that in this task we assume that $0^0 = 1$.

## Input
The first input line has an integer nn: the number of calculations.

After this, there are nn lines, each containing three integers $a$, $b$ and $c$.
$1≤n≤10^5$
$0≤a,b,c,≤10^9$

## Output
Print the answer.

## 解題思路
用fast_pow計算，注意$b^c$不能直接$\%\ 10^9+7$，運用費馬小定理
$$𝑎^𝑝≡𝑎(mod\ 𝑝) \implies a^{𝑝−1} ≡1(mod\ 𝑝)$$
把$b^c\ \%\ 10^9+6$使結果不變

## Code

#include <iostream>

unsigned int fast_pow(unsigned int a, unsigned int b, unsigned int m) {
    unsigned long long int ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % m;
        b >>= 1;
        a = (1ULL * a * a) % m; 
    }
    return ans;
}



int main() {
    int n;
    std::cin >> n;
    while (n--) {
        unsigned int a, b, c;
        std::cin >> a >> b >> c;
        // a^(p-1) ≡ 1 (mod p), a^(b^c) ≡ a^(b^c % (p-1))
        std::cout << fast_pow(a, fast_pow(b, c, 1000000006), 1000000007) << std::endl;
    }
    return 0;
}