题目描述

给你三个整数n、A和B。
定义：Si=A^i%B，Ti=min(Sk|i-A<=k<=i,k>=1)
您的任务是计算：T1*T2*...*Tn%B

输入格式

每行包含三个整数n(1 <= n <= 10^7)，A和B(1 <= A, B <= 2^31-1).

输出格式

对于每种情况，输出一行答案。

样例数据

input

1 2 3
2 3 4
3 4 5
4 5 6
5 6 7

output

2
3
4
5
6