# UVa 374

## Summary

A text book problem.

## Explanation

We are asked to compute ${\displaystyle b^{p}{\bmod {m}}}$. Using Repeated Squaring, we can calculate ${\displaystyle b^{p}}$ efficiently, so long as the individual multiplications aren't expensive. Just our luck, the modulus in the expression will keep the final result low. We can use the relation that ${\displaystyle (x\times y){\bmod {m}}=((x{\bmod {m}})\times (y{\bmod {m}})){\bmod {m}}}$ to keep the intermediate results small. Thus, we can use a basic integer to hold intermediate results, and never have to resort to BigNum multiplications.

## Input

3
18132
17

17
1765
3

2374859
3029382
36123


## Output

13
2
13195