Description

The fibonacci numbers are as follows:

f[1] = 1; f[2] = 2;

f[n] = f[n - 1] + f[n - 2];

And s[n] is defined:

s[n]=f[1]f[1]+f[2]f[2]+…+f[n]*f[n]

Now ,give you the integer number a, x and n, you should calculate the ans, and the ans is defined as follows:

ans = (a^s[x]) % n;

You must pay attention to the range of the number: 1 ≤ a ≤ 100000000; 1 ≤ x ≤ 1000000000; 2 ≤ n ≤ 100000000.

Input

The input contains several test cases. For each test case, only line contains three integer numbers a, x and n separated by spaces.

The end of the input is indicated by a line containing three zeros separated by spaces.

Output

For each test case the output is only one integer number ans in a line.

Sample

Input

1 1 100
2 3 1000000
0 0 0

Output

1
16384

Source: zjut_DD