CF1467D.Sum of Paths

There are $n$ cells, numbered $1,2,\dots, n$ from left to right. You have to place a robot at any cell initially. The robot must make exactly $k$ moves.

In one move, the robot must move one cell to the left or right, provided that it doesn't move out of bounds. In other words, if the robot was in the cell $i$, it must move to either the cell $i-1$ or the cell $i+1$, as long as it lies between $1$ and $n$ (endpoints inclusive). The cells, in the order they are visited (including the cell the robot is placed), together make a good path.

Each cell $i$ has a value $a_i$ associated with it. Let $c_0, c_1, \dots, c_k$ be the sequence of cells in a good path in the order they are visited ($c_0$ is the cell robot is initially placed, $c_1$ is the cell where the robot is after its first move, and so on; more formally, $c_i$ is the cell that the robot is at after $i$ moves). Then the value of the path is calculated as $a_{c_0} + a_{c_1} + \dots + a_{c_k}$.

Your task is to calculate the sum of values over all possible good paths. Since this number can be very large, output it modulo $10^9 + 7$. Two good paths are considered different if the starting cell differs or there exists an integer $i \in [1, k]$ such that the current cell of the robot after exactly $i$ moves is different in those paths.

You must process $q$ updates to $a$ and print the updated sum each time. Each update changes the value of exactly one cell. See the input format and the sample input-output for more details.

有 $n$ 个单元格，从左到右依次编号为 $1,2,\dots, n$。你必须初始时将一个机器人放置在任意一个单元格上。该机器人必须恰好执行 $k$ 次移动。

每次移动中，机器人必须向左或向右移动一个单元格，且不能移出边界。换言之，若机器人当前位于单元格 $i$，则它必须移动至单元格 $i-1$ 或 $i+1$，前提是该目标单元格位于 $1$ 到 $n$ 之间（含端点）。按访问顺序（包括机器人初始放置的单元格）所经过的所有单元格构成一条好路径（good path）。

每个单元格 $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$ 取模的结果。若两条好路径的起始单元格不同，或存在某个整数 $i \in [1, k]$，使得机器人在恰好执行 $i$ 次移动后所处的单元格不同，则认为这两条路径不同。

你需要处理 $q$ 次对数组 $a$ 的更新，并在每次更新后输出更新后的总和。每次更新恰好修改一个单元格的值。更多细节请参见输入格式及样例输入输出。

The first line of the input contains three space-separated integers $n$, $k$ and $q$ ($2 \le n \le 5000$; $1 \le k \le 5000$; $1 \le q \le 2 \cdot 10^5$).

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

$q$ lines follow. Each line contains two space-separated integers $i$ and $x$ ($1 \le i \le n$; $1 \le x \le 10^9$) indicating that you must change the value of $a_i$ to $x$.

输入的第一行包含三个以空格分隔的整数 $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$。

Print $q$ integers. The $i$-th integer should be the sum of values over all good paths after the first $i$ updates are performed. Since the answers may be large, print them modulo $10^9 + 7$.

输出 $q$ 个整数。其中第 $i$ 个整数应为执行前 $i$ 次更新后，所有“好路径”上数值之和。由于答案可能很大，请对 $10^9 + 7$ 取模后输出。

In the first example, the good paths are $(1, 2), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3), (4, 5), (5, 4)$.

Initially the values of $a$ are $[3, 5, 1, 4, 2]$. After the first update, they become $[9, 5, 1, 4, 2]$. After the second update, they become $[9, 4, 1, 4, 2]$, and so on.

在第一个例子中，好路径为 $(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]$，依此类推。