路径价值之和

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有 $n$ 个从左到右编号为 $1,2,\ldots,n$ 的格子。一个机器人可以从任意格子出发，并且必须恰好移动 $k$ 步。每一步只能移动到相邻格子，且不能越过边界。

每个格子 $i$ 有权值 $a_i$。一条路径的价值是机器人在初始位置以及每一步到达位置的权值之和。求所有不同路径的价值总和，对 $10^9+7$ 取模。

接下来有 $q$ 次单点修改。每次修改一个格子的权值后，输出当前所有路径的价值总和。

输入格式

第一行三个整数 $n,k,q$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行两个整数 $i,x$，表示把 $a_i$ 修改为 $x$。

输出格式

输出 $q$ 行，每行一个整数，表示对应修改后的答案对 $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

数据范围

$2\le n\le 5000$，$1\le k\le 5000$，$1\le q\le 2\times 10^5$，$1\le a_i,x\le 10^9$。