题目描述

人是不同的。有些人偷偷看充满了有趣的女孩的杂志，有些人在地窖里制造原子弹，有些人喜欢使用WINDOWS，有些人喜欢数学游戏。最新的市场调查显示，这一细分市场目前被低估了，而且缺乏这样的游戏。这种游戏因此被纳入了科科达克运动。运动的遵循的规则:

每个玩家选择两个数字$A_i$和$B_i$，并把它们写在一张纸条上。其他人看不到这些数字。在一个特定的时刻，所有的玩家都会向其他玩家展示他们的数字。目标是确定包括自己在内的所有玩家的所有表达$A_i^{B_i}$的总和，并用给定的数字$M$确定除法后的余数。获胜者是首先决定正确结果的人。根据玩家的经验，可以通过选择更高的数字来增加难度。

你应该编写一个程序来计算结果，并找出谁赢了这场比赛。

输入格式

第一行，一个数字$z$，表示有$z$组测试数据

每组测试数据第一行一个整数$M$,表示需要取模的数字

每组测试数据第二行一个整数$H$,表示有$H$组$A_i$和$B_i$

每组测试数据接下来有$H$行，在每一行上，有两个数字$A_i$和$B_i$被空间隔开。两个数不能同时等于零

输出格式

对于每组测试数据，只有一行输出。这一行有一个数字，就是以下表达式的结果

$(A_1^{B_1}+A_2^{B_2}+ ... +A_H^{B_H})mod M.$

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

2
13195
13

数据范围

$M (1 \leqslant M \leqslant 45000)$

$H(1 \leqslant H \leqslant 45000)$

来源

• POJ1995
• CTU Open 1999
• 算法竞赛进阶指南