暂无测试数据。

一个长度为 $n$ 的数组，每秒都在发生变幻。

每一次变幻，第 $1$ 个位置的数字将会和第 $2$ 个位置的数字合并，第 $3$ 个位置的数字将会和第 $4$ 个位置的数字合并…如果长度为奇数，则最后一个数字不会合并。以此类推。

这个数组会一直变幻到只剩两个数字为止。

合并数字时，将会使得两个数字相加。例如数组 $[1,2,3,4,5]$ 第一秒会变成 $[3,7,5]$（前两个数字合并，第三和第四个数字合并，由于没有第六个数字，所以第五个数字不变）第二秒会变成 $[10, 5]$，此时数组中只剩两个数字，变幻结束。

现在白浅妹妹想知道最后的两个数字的平方和是多少。例如上述数组，平方和为 $10\times 10 + 5\times 5 = 125$。

由于这个数组长度很大，所以白浅妹妹在给你数据时采用了一种新的方式。白浅妹妹总共会给出 $k$ 条信息，每条信息包含两个正整数 $a, b$，表示这个数组中有一段长度为 $a$ 的区间，区间中所有数字均为 $b$。（详见样例）

由于答案可能很大，请输出答案对 $10^9 + 7$ 取模之后的结果

输入格式

第一行给出两个正整数 $n, k$，意义如题面所示。

接下来 $k$ 行分别给出两个正整数 $a, b$。表示数组有 $a$ 个数字 $b$，保证区间是从左到右连续的。

输出格式

输出变幻到最后的两个数字的平方和。

数据范围

对于 30% 的数据，满足 $k \leq n \leq 10^3$

对于 60% 的数据，满足 $n \leq 10^5$

对于 100% 的数据，满足 $2 \leq n \leq 10^{18}, 1 < k \leq 10^5, \sum_{i = 1}^{k} a_i = n, a_i \geq 1, 1 \leq b_i \leq 10^9$。

请注意，答案要对 $10^9 + 7$ 进行取模。

5 5
1 1
1 2
1 3
1 4
1 5

125

7 2
3 1
4 2

61