一个长度为 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，保证区间是从左到右连续的。
输出变幻到最后的两个数字的平方和。
5 5 1 1 1 2 1 3 1 4 1 5
125
7 2 3 1 4 2
61
对于 30% 的数据，满足 k≤n≤10^3
对于 60% 的数据，满足 n≤10^5
对于 100% 的数据，满足 2≤n≤10^{18},1<k≤10^5,\sum_{i=1}^ka_i=n,a_i≥1,1≤b_i≤10^9 。
请注意，答案要对 10^9+7 进行取模。
样例解释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]，此时数组只剩两个数字，我们对其求平方和，得到 55+66 = 61