题目描述

有一个叫做 KOKODáKH 的游戏。它的规则是这样的：

游戏玩家总共有 $n$ 个人，每个人都会获得两个数，且第 $i$ 个人的数由 $a_i,b_i$ 来表示。

每个人都需要计算 $a_i^{b_i}$ 的结果，而小乔作为游戏的组织者需要把这些数的和算出来。

由于结果可能非常大，小乔在征得 Gordon 的同意后，发现他只需要去计算这个和对 Gordon 给他的数 $m$ 取模的结果。

输入格式

第一行两个数 $m,n(1\le m,n\le 45000)$。

往后 $n$ 行中的第 $i$ 行有两个整数 $a_i,b_i(1\le a_i,b_i\le 10^6)$。

输出格式

一个数，为最后的结果。

16 4
2 3
3 4
4 5
5 6

2