3281: 高级模运算

人与人是不同的,有些人喜欢阅读满是图片的杂志，有些人喜欢在地下室引爆炸弹，而还有一些却喜欢一些麻烦的数字游戏。比如ESSE论坛的一次活动：每个人选择两个数字Ai和Bi写在纸上，其他人不能看见。过了一段时间后，每个人说出自己纸上的数字，然后每个人的目标是求出所有的Ai^Bi的和模M的值，最先算出结果的，就是胜利者。作为一个程序员，你当然有办法便一个程序，以最快的速度算出结果，赢得比赛。

第一行是一个数字M (1 <= M <= 45000)。第二行是数字H（1 <= H <= 45000）表示参加游戏的人数。接下来H行，每行两个数Ai和Bi（1<=Ai，Bi<=2³¹）。

输出一个数字， (A1^B1+ A2^B2 + ... + AH^BH) mod M  的值。

16
4
2 3
3 4
4 5
5 6

2