eolymp
bolt
Try our new interface for solving problems
Problems

A^B mod C

A^B mod C

Time limit 1 second
Memory limit 128 MiB

Given a, b, c find the value of a^(b) mod c (1a, b, c < 2^63).

Input data

Contains multiple test cases. Each test is given in one line and contains three integers a, b and c.

Output data

For each test case print on a separate line the value of a^(b) mod c.

Examples

Input example #1
3 2 4
2 10 1000
Output example #1
1
24
Source Stage II All-Ukrainian Olympiad 2010-2011 Berdichev