灰灰的KPS / 【模板】快速幂

灰灰的KPS / 【模板】快速幂

题目描述

我不是音游人,不会KPS的计算方式,这里只是引用KPS的概念(

灰灰又打开了他钟爱的冰与火之舞!这已经是他在steam上玩冰与火的第114514个小时了。
因为单身了16年,灰灰的手速现在已经快到离谱,他经常在MPT管理群里炫耀他的KPS(Keys Per Second)。
今天灰灰又跳出来炫耀手速。他给出了一个公式:\(KPS = A^B\ mod\ P\)
\(A\)为单身年数,\(B\)为牛牛长度(?),\(P\)为游玩小时数。
听灰灰这样说之后,MPT群里群里的每一个人都想试试计算出自己的KPS。请你帮帮MPT大佬计算他们的KPS。

输入格式

第一行一个整数\(M\),表示数据组数。
接下来的\(M\)行,每行三个整数,分别为\(A, B, P\)

输出格式

对于从第二行开始的每组数据,输出一个整数为该组的计算结果。

样例

输入

3 
2 10 9
3 6 29
3 1 3

输出

7
4
0

数据规模与约定

对于\(100%\)的数据,保证\(0 \leqslant a, b < 2^31, a + b > 0, 2 \leqslant p < 2^31, 0 < m \leqslant 10\)

信息

ID
1005
难度
3
分类
快速幂 点击显示
标签
递交数
9
已通过
4
通过率
44%
上传者

相关