#6716. 自然数幂之和

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: JKLover

题目描述

给出 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 为质数