人与人是不同的,有些人喜欢阅读满是图片的杂志，有些人喜欢在地下室引爆炸弹，而还有一些却喜欢一些麻烦的数字游戏。
每个人选择两个数字Ai和Bi写在纸上，其他人不能看见。过了一段时间后，每个人说出自己纸上的数字，然后每个人的目标是求出所有的AiBi的和再模M的值，最先算出结果的，就是胜利者。
作为一个程序员，你当然有办法编一个程序，以最快的速度算出结果，赢得比赛。
第一行是一个数字M (1 <= M <= 45000)。第二行是数字H（1 <= H <= 45000）表示参加游戏的人数。接下来H行，每行两个数Ai和Bi（1<=Ai，Bi<2^31），之间用一个空格隔开。
输出一个数字， (A1B1+ A2B2 + ... + AHBH) mod M 的值。
16
4
2 3
3 4
4 5
5 6
2