# UVa 374

From Algorithmist

## 374 - Big Mod[edit]

## Summary[edit]

A text book problem.

## Explanation[edit]

We are asked to compute . Using Repeated Squaring, we can calculate 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 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[edit]

3 18132 17 17 1765 3 2374859 3029382 36123

## Output[edit]

13 2 13195