A^B mod C#1121

A^B mod C

1 секунда

128 мегабайт

Medium

Для заданных $a$ , $b$ , $c$ вычислите значение $a^{b} mod c$ a^{b} \bmod c ( $1 \leq a, b, c < 2^{63}$ 1 \leq a, b, c < 2^{63}).

Состоит из нескольких тестов. Каждый тест задаётся в одной строке и содержит три числа $a$ , $b$ и $c$ .

Для каждого теста в отдельной строке выведите результат вычисления $a^{b} mod c$ a^{b} \bmod c.

Examples

Example 1

Loading

a^{b} mod c

1 \leq a, b, c < 2^{63}

a^{b} mod c