题目描述

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

每一次变幻，第 1 个位置的数字将会和第 2 个位置的数字合并，第 3 个位置的数字将会和第 4 个位置的数字合并，以此类推。。

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

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

现在小核桃想知道最后的两个数字的平方和是多少。例如上述数组，平方和为 10*10 + 5*5 = 125

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

由于答案可能很大，请对 $10^9 + 7$ 取模

输入格式

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

接下来 $k$ 行分别给出两个正整数 $a, b$。表示数组有 $a$ 个数字 $b$。注意，本题保证所有 $a$ 的和为 $n$，$b$ 的数据范围至多 100。

输出格式

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

样例 #1

样例输入 #1

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

样例输出1

125

样例 #2

样例输入 #2

7 2
3 1
4 2

样例输出 #2

61

数据范围及提示

【样例解释 #1】

样例中给出 1 个 1，1 个 2，1 个 3，1 个 4， 1 个 5。数组的内容和合并过程就是题面中的示例，答案为 125。

【样例解释 #2】

样例中给出了 3 个 1 和 4 个 2，即数组为 [1,1,1,2,2,2,2]，第一秒变为 [2,3,4,2]，第二秒变为 [5,6]，此时数组只剩两个数字，我们对其求平方和，得到 5*5+6*6 = 61

【数据范围】

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

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

对于 80% 的数据，满足 $1 \leq n \leq 10^{10}$

对于 100% 的数据，满足 $1 \leq a_i \leq n < 10^{18}, 1 \leq k \leq 10^5$。请注意，答案要对 $10^9 + 7$ 进行取模