问题 F: 模仿快速幂取模运算

问题 F: 模仿快速幂取模运算

时间限制: 1 Sec  内存限制: 128 MB
提交: 468  解决: 88
[状态] [讨论版] [提交] [命题人:]
题目描述

n个a数相乘,是a的n次幂,对于a的n次幂,我们可以用一种快速幂的方法去实现。

如下函数Pow是计算a的b次幂对mod取模(取余数):

其实,对于n个a相加,我们也可以用这种思想
现在,请计算n个a相加的值,对mod取余后的结果

输入
T组测试数据(T<=1000)
对于每组测试数据,输入三个整数,n, a, mod(n,a,mod<=1e17)
输出
每组样例输出一行,输出n个a相加的值,对mod取余后的结果
样例输入 Copy
1
9 3 10
样例输出 Copy
7