苏老师的数组变换
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
说明
苏老师有一个长度为 $n$ 的数组，但是这个数组发生了一些奇妙的变化——每一秒这个数组都在不断的收缩！
每一秒，相邻的两个数字会合并成一个，产生一个新的数组，一直搜索到数组只剩下两个数字
每一次的合并，就是将两个数字相加
例如有一个长度为 $5$ 的数组 `[1,2,3,4,5]`
第一秒：会合并 $(1,2),(3,4)$，因为没有第六个数字，所以 $5$ 不变，即变成新数组 `[3,7,5]`
第二秒：会合并 $(3,7)$，因为没有第四个数字，所以 $5$ 不变，即变成新数组 `[10,5]`
此时，数组收缩到只有两个数字，结束变化
现在苏老师想知道，这个数组最后两个数字的平方和会是多少？
输入格式
第一行给出两个正整数 $n,k$，$n$ 表示数组长度，$k$ 表示输入数据组数
接下来 $k$ 行，每行包含两个整数 $x,y$ 表示数组接下去有 $x$ 个数字 $y$，具体请看样例解释
对于 $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 n < 10^{18}, 1 \leq k \leq 10^5, 1 \leq x \leq 10^6, 1 \leq y \leq 10^9$。
特别的保证：对于所有数据满足 $\sum{x} = n$
输出格式
输出最后两个数字的平方和，由于答案可能很大，请对 $10^9 + 7$ 取模
样例
7 2
3 1
4 261提示
输入给出了 个 和 个 ，即数组为 ，第一秒变为 ，第二秒变为 ,答案即为
2023普及组模拟赛2
- Status
- Done
- Rule
- OI
- Problem
- 4
- Start at
- 2023-10-2 8:30
- End at
- 2023-10-2 18:30
- Duration
- 3.5 hour(s)
- Host
-
sulaoshi
- Partic.
- 2