柯南的数学题

Time Limit: 1000MS

Memory Limit: 131072KB

Description

众所周知,柯南小童鞋是一个高智商的小学生。

一天,他碰到了一道奇怪的数学题:求函数值f(n) = (a ^ g(n))% p,其中p一定为质数,

而函数g(n)在旁边有这样一段话:@#¥%……&×@#¥%……&×,njust,{1,1,0,0,0}。

柯南童鞋完全看不懂那句话,通过猜测,他明白了,g(n)函数是指njust五个字母,可重复出现,并且其中“n”与“j”两个字母必须出现,且以奇数个出现,“u”“s”“t”没有限制条件的情况下,总共出现n个的排列数。柯南童鞋这下犯难了,这要计算太多了,所要柯南童鞋请你写程序帮他解决这个问题。


Input

每个样例一行,格式为:a n p,意思如题目所言。

0<=a,n<=2^31-1.,1<p<1000000


Output

对于每个样例在一行中输出f(n)。

Sample Input

2 2 7
1 3 11

Sample Output

4
1

Hint

None

Source

None

提交代码