模幂和问题

题目描述

给定 $H$ 对非负整数数对 $(A_i, B_i)$ 和一个正整数 $M$。

对于任意数对 $(A_i, B_i)$，定义 $f(A_i, B_i) = A_i^{B_i} \bmod M$。

请计算 $\displaystyle \left( \sum_{i=1}^H f(A_i, B_i) \right) \bmod M$ 的值。

输入格式

输入以如下格式从标准输入读入。

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据格式如下：

$M$
$H$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_H$ $B_H$

输出格式

对于每组测试数据，输出一行答案。

输入输出样例 #1

输入 #1

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

输出 #1

2
13195
13

输入输出样例 #2

输入 #2

1
10
3
1 5
2 3
3 2

输出 #2

0

限制条件

• $1 \le T \le 100$
• $1 \le M \le 45000$
• $1 \le H \le 45000$
• $0 \le A_i, B_i \le 10^7$
• $A_i$ 和 $B_i$ 不同时为 $0$
• 所有输入均为整数

样例解释 1

对于第一组数据：

• $(2^3 \bmod 16) = 8$
• $(3^4 \bmod 16) = 81 \bmod 16 = 1$
• $(4^5 \bmod 16) = 1024 \bmod 16 = 0$
• $(5^6 \bmod 16) = 15625 \bmod 16 = 9$
• 总和为 $8 + 1 + 0 + 9 = 18$
• $18 \bmod 16 = 2$

因此输出 $2$。

对于第二组数据：

• $(2374859^{3029382} \bmod 36123) = 13195$

对于第三组数据：

• $(3^{18132} \bmod 17) = 13$