CF1467D Sum of Paths

有 $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$ 取模的结果。如果起始格子不同，或者存在某个 $i \in [1, k]$ 使得机器人移动 $i$ 步后所在的格子不同，则两条路径被认为是不同的。 你需要处理 $q$ 次对 $a$ 的修改，并在每次修改后输出更新后的总价值。每次修改会改变恰好一个格子的权值。具体输入输出格式见下文和样例。

第一行包含三个用空格分隔的整数 $n$、$k$ 和 $q$（$2 \le n \le 5000$；$1 \le k \le 5000$；$1 \le q \le 2 \times 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, 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]$，以此类推。 由 ChatGPT 4.1 翻译