#描述#
The fibonacci numbers are as follows:
<BR>
f[1] = 1; f[2] = 2;
<BR>
f[n] = f[n - 1] + f[n - 2];
<BR>
<BR>
And s[n] is defined:
<BR>
s[n]=f[1]*f[1]+f[2]*f[2]+…+f[n]*f[n]
<BR>
<BR>
<BR>

Now ,give you the integer number a, x and n, you should calculate the ans, and the ans is defined as follows:
<BR>
ans = (a^s[x]) % n;
<BR>
<BR>
<BR>

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

#格式#
##输入格式##
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.

##输出格式##
For each test case the output is only one integer number ans in a line.

#样例1#
##样例输入1##

1 1 100
2 3 1000000
0 0 0

##样例输出1##

1
16384

#限制#
1000ms
32768KB

#提示#

#来源#
zjut_DD