Home => ProblemSet => 2.8-03:求和
Problem1217--2.8-03:求和

1217: 2.8-03:求和

Time Limit: 2 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给定 n,k 和 m,请你计算: (1^k +2^k +3^k +…+n^k) mod m

Input

输入数据 一行,三个整数,n,k,m

Output

一行,(1k +2k +3k +…+nk) mod m

Sample Input Copy 

4 3 98

Sample Output Copy 

2

HINT

数据规模
1 ：n≤2^63 −1,k=1,m≤2^31 −1
2-3：n ≤ 10^6,k ≤ 100,m ≤ 10^7
4-5：n ≤ 10^8,k ≤ 10^7,m ≤ 3 ∗ 10^7
6-10：n ≤ 2^63 −1,k ≤ 2^63 −1,m ≤ 1.5∗10^6

Source/Category

fj 夏令营 算法 快速幂 
[ Submit ] [ Status ]