题目描述

给出 $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$ 次询问的答案。

样例

input

10 2
2 5
3 3

output

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