Problem: There are n cells, numbered 1,2,..., 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, ..., 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} + ... + 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 ∈ [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.

Input

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

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

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

Output

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.

Examples

Input


5 1 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2


Output


62
58
78
86
86


Input


5 2 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2


Output


157
147
207
227
227


Input


4 40 6
92 21 82 46
3 56
1 72
4 28
1 97
2 49
2 88


Output


239185261
666314041
50729936
516818968
766409450
756910476

Note

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.

Solution (in CPP):

Solution:
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;


typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> pr;
typedef pair<LL, LL> lpr;
typedef pair<double, double> dbpr;
typedef pair<long double, long double> ldpr;
typedef double db;
typedef long double ld;

#define dbgs(x) #x << " = " << x
#define dbgs2(x, y) dbgs(x) << ", " << dbgs(y)
#define dbgs3(x, y, z) dbgs2(x, y) << ", " << dbgs(z)
#define dbgs4(w, x, y, z) dbgs3(w, x, y) << ", " << dbgs(z)

#define mst(s, x) memset(s, x, sizeof(s))
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define all(x) x.begin(), x.end()
#define unq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define fp(i, a, b) for (int i = (a), I = (b) + 1; i < I; ++i)
#define fd(i, a, b) for (int i = (a), I = (b)-1; i > I; --i)
#define ub upper_bound
#define lb lower_bound
#define bitcount __builtin_popcount
#define sqr(x) ((x)*(x))

#define go(u) for (int i = pre[u], v = e[i].v; i; i = e[i].next, v = e[i].v)
#define gow(u) for (LL i = pre[u], v = e[i].v, w = e[i].w; i; i = e[i].next, v = e[i].v, w = e[i].w)
#define EDGE(N,M) struct edge{int u,v,w,next;}e[M];int pre[N],edge_cnt=0;void addedge(int u,int v,int w=0){edge_cnt=edge_cnt+1,e[edge_cnt].u=u,e[edge_cnt].v=v,e[edge_cnt].w=w,e[edge_cnt].next=pre[u],pre[u]=edge_cnt;}
#define CLEAR_EDGE(N) {edge_cnt=0,memset(pre,0,sizeof(int)*(N+1));}

#define MC int _CASE;scanf("%d",&_CASE);fp(case_num,1,_CASE)

const int next_x[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int next_y[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int inf = 1e9+5;//7; 
const LL linf = 1e15;
const db  PI  = acos(-1.0);

const int MAXN  = 5000+5;
const int N     = 1e6+5;
const int M     = 1;
const ld eps    = 1e-8;

#define mid ((l+r)>>1)+
#define ls (cnt<<1)
#define rs (cnt<<1|1)

// #define ls ch[x][0]
// #define rs ch[x][1]

/*----------head----------*/

const LL MOD = 1e9+7;
int n,k,q;
LL a[MAXN],f[MAXN][MAXN],b[MAXN];
void mo(LL &x){x%=MOD,x+=MOD,x%=MOD;}
int main()
{
	scanf("%d%d%d",&n,&k,&q);
	fp(i,1,n)scanf("%lld",&a[i]);
	fp(i,1,n)f[i][0]=1;
	fp(j,1,k)fp(i,1,n)
	{
		f[i][j]=0;
		if(i>=2)f[i][j]+=f[i-1][j-1];
		if(i< n)f[i][j]+=f[i+1][j-1];
		f[i][j]%=MOD;
	}

	LL ans=0;
	fp(i,1,n)fp(j,0,k)b[i]+=f[i][j]*f[i][k-j]%MOD,b[i]%=MOD;
	fp(i,1,n)ans=(ans+a[i]*b[i]%MOD)%MOD;
	while(q--)
	{
		int i,x;scanf("%d%d",&i,&x);
		ans-=(a[i]*b[i])%MOD,mo(ans);
		a[i]=x;
		ans+=(a[i]*b[i])%MOD,mo(ans);
		printf("%lld\n",ans);
	}
	return 0;
}


// 函数不返回值可能会 RE
// 少码大数据结构，想想复杂度更优的做法
// 小数 二分/三分 注意break条件
// 浮点运算 sqrt(a^2-b^2) 可用 sqrt(a+b)*sqrt(a-b) 代替，避免精度问题
// long double -> %Lf 别用C11 (C14/16)
// 控制位数 cout << setprecision(10) << ans;
// reverse vector 注意判空 不然会re
// 分块注意维护块上标记 来更新块内数组a[]
// vector+lower_bound常数 < map/set/(unordered_map)
// map.find不会创建新元素 map[]会 注意空间
// 别对指针用memset
// 用位运算表示2^n注意加LL 1LL<<20
// 注意递归爆栈
// 注意边界  
// 注意memset 多组会T