题目描述

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

输入格式

第一行是一个数字M (1 <= M <= 45000)。第二行是数字H（1 <= H <= 45000）表示参加游戏的人数。接下来H行，每行两个数Ai和Bi（1<=Ai，Bi<=2^31），之间用一个空格隔开。

输出格式Format

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

样例数据

input

16
4
2 3
3 4
4 5
5 6

output

2

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$