G. *【快速幂】幂函数序列求和[POJ1995]

传统题

1000ms

64MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

0x00基本算法（0x01位运算）例题4：Raising Modulo Numbers

【题意】

求 $S=(A_1^{B_1}+A_2^{B_2}+……+A_n^{B_n}) \bmod M$ 的值。

第一行一个整数 $T$ ，表示下来有 $T$ 组数据。每一组数据的描述如下：第一行一个整数 $M (1 \le M \le 45000)$ ，第二行一个整数 $n (1 \le n \le 45000)$ 。下来n行，每行两个整数 $A_i$ 和 $B_i$ （都不为0）。

每组数据输出一行一个整数，即 $S$ 的值。

3
16
4
2 3
3 4
4 5
5 6
36123
1
2374859 3029382
17
1
3 18132

【样例输出】

2
13195
13