有 $$$n$$$ 个单元格,从左到右编号为 $$$1,2,\dots, n$$$。您最初必须将机器人放置在任何单元格中。机器人必须精确地进行 $$$k$$$ 移动。
在一次移动中,机器人必须向左或向右移动一个单元格,前提是它不移出边界。换句话说,如果机器人位于单元格 $$$i$$$ 中,则它必须移动到单元格 $$$i-1$$$ 或单元格 $$$i+1$$$,只要它位于 $$$1$$$ 和 $$$n$$$ 之间(包括端点)。这些单元按照访问的顺序(包括机器人放置的单元)一起形成一条良好的路径。
每个单元格 $$$i$$$ 都有一个与其关联的值 $$$a_i$$$。令 $$$c_0, c_1, \dots, c_k$$$ 为良好路径中的单元序列,按照它们被访问的顺序排列($$$c_0$$$ 是单元机器人最初放置的单元,$$$c_1$$$ 是机器人在第一次移动后所在的单元,依此类推;更正式地说,$$$c_i$$$ 是机器人在 $$$i$$$ 移动后所在的单元)。然后路径的值计算为 $$$a_{c_0} + a_{c_1} + \dots + a_{c_k}$$$。
您的任务是计算所有可能的良好路径的值总和。由于这个数字可能非常大,因此输出它对 $$$10^9 + 7$$$ 取模。如果起始单元不同或 [1, k]$$$ 中存在整数 $$$i \in 使得机器人在 $$$i$$$ 移动后的当前单元在这些路径中不同,则认为两条好路径不同。
您必须处理 $$$q$$$ 对 $$$a$$$ 的更新,并每次打印更新后的总和。每次更新都会更改一个单元格的值。有关更多详细信息,请参阅输入格式和示例输入输出。
输入
输入的第一行包含三个空格分隔的整数 $$$n$$$、$$$k$$$ 和 $$$q$$$ ($$$2 \le n \le 5000$$$; $$$1 \le k \le 5000$$$; $$$1 \le q \le 2 \cdot 10^5$$$)。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。 接下来是
$$$q$$$ 行。每行包含两个空格分隔的整数 $$$i$$$ 和 $$$x$$$ ($$$1 \le i \le n$$$; $$$1 \le x \le 10^9$$$),表示必须将 $$$a_i$$$ 的值更改为 $$$x$$$。
输出
打印 $$$q$$$ 整数。第 $$$i$$$ 个整数应该是执行第一个 $$$i$$$ 更新后所有良好路径上的值之和。由于答案可能很大,请以 $$$10^9 + 7$$$ 为模打印它们。
示例
输入 #1
5 1 5 3 5 1 4 2 1 9 2 4 3 6 4 6 5 2
输出 #1
62 58 78 86 86
输入 #2
5 2 5 3 5 1 4 2 1 9 2 4 3 6 4 6 5 2
输出 #2
157 147 207 227 227
输入 #3
4 40 6 92 21 82 46 3 56 1 72 4 28 1 97 2 49 2 88
输出 #3
239185261 666314041 50729936 516818968 766409450 756910476
注意
在第一个示例中,好的路径是 $$$(1, 2), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3), (4, 5), (5, 4)$$$。
最初 $$$a$$$ 的值为 $$$[3, 5, 1, 4, 2]$$$。第一次更新后,它们变成 $$$[9, 5, 1, 4, 2]$$$。第二次更新后,它们变成$$$[9,4,1,4,2]$$$,依此类推。