提示: 欢迎访问OurACM平台。
Problem 1759 Super A^B mod C

Accept: 1231    Submit: 4161
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,C<=1000000000,1<=B<=10^1000000).

Input

There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.

Output

For each testcase, output an integer, denotes the result of A^B mod C.

Sample Input

3 2 4 2 10 1000

Sample Output

1 24

Source

FZU 2009 Summer Training IV--Number Theory

Submit  Back  Status  Discuss