#6716. 自然数幂之和

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

给出 $m$ 次询问和一个模数 $P$ ，每次询问给出两个正整数 $n,k$ ，需要求出 $S(n,k)=\sum_{i=1}^n i^k \bmod P$ 的值。

需要注意， $P$ 不一定为质数。

共 $m+1$ 行。

第一行读入两个正整数 $P,m$ 。

接下来的 $m$ 行，每行读入两个正整数 $n,k$ ，表示该次询问需要求出 $S(n,k)$ 。

共 $m$ 行。

第 $i$ 行输出一个非负整数，表示第 $i$ 次询问的答案。

输入

10 2
2 5
3 3

输出

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$ 为质数。