【一点关于出题者诚信问题的说明】有同学说可能见过这道题，但我真的是原创，只是刚好碰上相同的罢了。
题目描述
LYC同学想出题考大家,然而他数学成绩很差,于是只能编出一些低成本数学题。
求b=(Ⅱgcd(i,a))%k (i∈[1,n])

输入格式
一行3个整数a，n，k（保证k为素数）

输出格式
一个整数为答案

输入样例
9 18 1000000007

输出样例
6561

样例说明
gcd分别为1，1，3，1，1，3，1，1，9，1，1，3，1，1，3，1，1，9

规定
对于30%的数据，可以暴力。
ai<=2^20
ni<=10^18