Power Sum

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

给出n,m,p,求 (1^m + 2^m + 3^m + 4^m + ... + n^m) % p

Input

第一行一个数T( <= 10),表示数据总数 

然后每行给出3个数n,m,p(1 <= n <= m <= 10^18, 1 <= p <= 10^6, p是质数

Output

每组数据输出你求得的结果

Sample Input

2
1 1 11
3 2 11

Sample Output

1
3

Hint

i^m即求 i * i * i * i * i... * i(m个i),比如2^3即2 * 2 * 2 

Source

dream

Manager

Information
Solved Number14
Submit Number203
Problem Tags
number theory
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel