A5999. 自然数幂之和
编程题
提高+/省选-
知识点
题目描述
给出 $m$ 次询问和一个模数 $P$，每次询问给出两个正整数 $n,k$，需要求出 $S(n,k)=\sum_{i=1}^n i^k \bmod P$ 的值。
需要注意，$P$ 不一定为质数。
需要注意，$P$ 不一定为质数。
输入格式
共 $m+1$ 行。
第一行读入两个正整数 $P,m$。
接下来的 $m$ 行，每行读入两个正整数 $n,k$，表示该次询问需要求出 $S(n,k)$。
第一行读入两个正整数 $P,m$。
接下来的 $m$ 行，每行读入两个正整数 $n,k$，表示该次询问需要求出 $S(n,k)$。
输出格式
共 $m$ 行。
第 $i$ 行输出一个非负整数，表示第 $i$ 次询问的答案。
第 $i$ 行输出一个非负整数，表示第 $i$ 次询问的答案。
输入输出样例
输入 #1
10 2 2 5 3 3
输出 #1
3 6
说明/提示
对于 $100\%$ 的数据，满足 $1\le m\le 50, 1\le P\le 10^9, 1\le n\le 10^9, 1\le k\le 10^4$。
**不保证模数 $P$ 为质数**。
**不保证模数 $P$ 为质数**。