**Little Panda** has a thing for powers and modulus and he likes challenges. His friend **Lucy**, however, is impractical and challenges **Panda** to find both positive and negative powers of a number modulo a particular number. We all know that \(A^{-1}\bmod X\) refers to the modular inverse of \(A\) modulo \(X\).

Since **Lucy** is impractical, she says that \(A^{-n}\bmod X=(A^{-1}\bmod X)^n \bmod X\) for \(n>0\) .

Now she wants **Panda** to compute \(A^B\bmod X\).

She also thinks that this problem can be very difficult if the constraints aren't given properly. **Little Panda** is very confused and leaves the problem to the worthy programmers of the world. Help him in finding the solution.

**Input Format**

The first line contains \(T\), the number of test cases.

Then \(T\) lines follow, each line containing \(A\), \(B\) and \(X\).

**Output Format**

Output the value of \(A^B\bmod X\).

**Constraints**

\(1\leq T\leq 1000\)

\(1\leq A\leq 10^6\)

\(-10^6\leq B\leq 10^6\)

\(1\leq X\leq 10^6\)

\(A\) and \(X\) are coprime to each other

**Sample Input**

```
3
1 2 3
3 4 2
4 -1 5
```

**Sample Output**

```
1
1
4
```

**Explanation***Case 1:* \(1^2\bmod 3=1\bmod 3=1\) *Case 2:* \(3^4\bmod 2=81\bmod 2=1\) *Case 3:* \(4^{-1}\bmod 5=4\)

## Solution

The solution is already implied by the statement. We need to check the sign of the exponent \(B\); if it's positive we can calculate the modular exponentation; if it's negative we need to calculate the modular inverse of \(A\) first. The modular inverse can be calculated quite easily using the extended euclidean algorithm, which finds the parameters \(s, t\) such that \(as+bt=\gcd(a,b)\). Implemented in Ruby, the egcd algorithm looks as follows:

```
def egcd(a, b)
return 1, 0 if b == 0
q, r = a.divmod b
s, t = egcd(b, r)
return t, s - q * t
end
```

Using the egcd, the modular inverse is given by:

```
def modinv(z, n)
return mod(egcd(z, n)[0], n)
end
```

Using a mathematical modulo operator:

```
def mod(n, m)
return (n % m + m) % m
end
```

The last piece to complete the task is an modular exponentation function:

```
def modpow(b, e, m)
r = 1
while e > 0 do
if e % 2 == 1 then
r = (r * b) % m
end
b = (b * b) % m
e >>= 1
end
return r
end
```

With all these helper functions, we can finally formulate the solution like this:

```
gets.to_i.times{
a, b, x = gets.split.map(&:to_i)
if b >= 0 then
puts modpow(a, b, x)
else
puts modpow(modinv(a, x), -b, x)
end
}
```

Another way to calculate the modular inverse uses Euler's theorem. Given two coprime numbers \(a\) and \(m\), it states

\[a^{\phi(m)}\equiv 1\pmod{m}\]

Dividing both sides by \(a\) reveals

\[a^{\phi(m)-1}\equiv a^{-1}\pmod{m}\]

However, I did not use it, since it requires a prime factorization of \(m\) which limits a possible improvement over the egcd alot.