The Big Powers

easyModular ExponentiationBinary Exponentiation

There are $$$n$$$ rounds. For each round, you are given three numbers: $$$a$$$, $$$b$$$, and modulus $$$m$$$.

You need to find $$$a^b \bmod m$$$.

If both $$$a = 0$$$ and $$$b = 0$$$, take $$$a^b$$$ as $$$1$$$.

Input Format:

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of rounds.

Each of the next $$$n$$$ lines contains three integers $$$a$$$, $$$b$$$, $$$m$$$ ($$$1 \leq a, b \leq 10^9$$$, $$$1 \leq m \leq 10^9 + 7$$$).

Output Format:

For each round, print $$$a^b \bmod m$$$ on its own line.

Examples:

Example 1:

Input:

3
1000 1 997
2 3 1
2 3 100

Output:

3
0
8

Example 2:

Input:

1
17 7 13

Output:

4

Code

Loading Editor...