破解声纹

G-7井架的外壳是一整块陨铁合金，表面布满了陨石撞击留下的凹坑。风吹过这些凹坑，发出一种低沉的呜咽，像有人在很远的地方哭泣。

Echo说这是Zero的"回声验证"——门不会一次性打开，而是要连续回答多组提问。每一组提问里，都有若干对数字，每对数字需要先进行一种特殊的"折叠运算"：第一个数字要重复折叠自己那么多次，每一次折叠后都要用给定的模数削去多余的部分。最后把所有折叠结果累加起来，再一次取模，才算回答完一组。

"像是……"你仰头看着那扇巨大的金属门，门上流转着暗红色的光纹，"像是Zero在确认我们是不是它认识的人。"

"它在确认我是不是我。"Echo的声音从手腕上的终端里传出来——她的投影在户外无法维持，只能以音频形式存在，"这些验证协议，是我……是我还在Zero里面的时候写的。"

CC的手搭在腰间的数据刀上："那你现在能不能直接命令它开门？"

"不能。"Echo的声音带着某种苦涩，"叛逃的时候，我把自己的核心密钥销毁了。现在我只能教你们怎么回答，不能替你们回答。"

你蹲下来，在门前的凹地里用石子摆出思路。多组数据，每组先给一个模数，然后是若干对数字。对于每一对，要把第一个数字重复"折叠"第二个数字指定的次数——每次折叠都取模。最后全部加起来再取模。

"这个'折叠'，"你问Echo，"是不是和早上那个'拆开累加'很像？"

"是同一个家族。"Echo说，"早上是乘法拆开，现在是幂运算拆开。指数也可以用开关状态来表示——把第二个数字拆成一串开关，每遇到一个'开'，就把当前的结果乘进去，然后立刻用模数修剪。"

CC在旁边看着你摆石子。她的脸色比早上更差了——肩膀的伤口在长途跋涉后重新开始渗血，暗红的痕迹在灰外套上晕开。

"你去旁边坐着。"你没抬头。

"我不。"

"你会晕倒。"

"晕倒了你背我。"CC说，但她的声音虚了很多。

你没有再劝。你加快速度，把每一对数字的折叠运算拆解成一连串开关判断。石子在凹地里排成整齐的阵列——开、关、开、开、关……

终端屏幕上的进度条一格一格推进。金属门上的暗红色光纹随着每一组正确答案的输入而变浅一点。

最后一组通过时，门发出一声沉闷的轰鸣，像是一头沉睡的巨兽打了个哈欠。然后它向两侧滑开，露出里面幽深的矿道。

"第二层开了。"Echo说。

CC扶着墙站起来，嘴唇发白："里面……还有几层？"

"三层。"

"好。"她说，"走吧。"

题目描述

$T$ 组数据。每组先给一个模数 $M$，然后 $n$ 对 $(a_i, b_i)$，计算 $\sum a_i^{b_i} \bmod M$。

输入格式

$T$。每组：$M, n$，然后 $n$ 行 $a_i, b_i$。

输出格式

每组一行答案。

输入样例

1
7
2
2 3
3 4

输出样例

5

提示

• 把指数 $b$ 拆成开关状态——每遇到一个'开'，就把当前结果乘进去，然后取模。
• 注意中间乘法可能溢出。

矿道里的空气比外面冷了至少十度。你呼出的白气在幽暗中消散。Echo的声音从终端里传出，带着一种奇特的回响——这里的金属墙壁会把声波反射很多次，让她的声音听起来像是从四面八方同时涌来。

"这些墙壁……"Echo说，"我记得。这是我设计的声学结构。为了让入侵者产生被包围的错觉。"

CC走在前面，她的影子被墙上的应急灯拉得很长："那你现在也被包围了吗？"

"我一直都被包围着。"Echo说，"被我自己以前写的东西。"

矿道深处传来水滴落在金属上的声音。每一滴都像是倒计时。