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