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.

Difficulty: HARD
Tags: Dynamic programming

Combinatorics

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0] * (k + 1) for i in range(n + 2)]
mod = 10 ** 9 + 7
for i in range(1, n + 1):
	dp[i][0] = 1
for j in range(1, k + 1):
	for i in range(1, n + 1):
		dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1]) % mod
c = [0] * n
for i in range(1, n + 1):
	for pos in range(k + 1):
		c[i - 1] += dp[i][pos] * dp[i][-pos - 1]
		c[i - 1] %= mod
total = sum((a[i] * c[i] % mod for i in range(n))) % mod
for _ in range(q):
	(i, x) = map(int, input().split())
	diff = a[i - 1] - x
	a[i - 1] = x
	total = (total - diff * c[i - 1]) % mod
	print(total)


import os
import sys
from io import BytesIO, IOBase
sz = 8192

class fio(IOBase):
	nl = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, sz))
			if not b:
				break
			pointer = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(pointer))
		self.nl = 0
		return self.buffer.read()

	def readline(self):
		while self.nl == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, sz))
			self.nl = b.count(b'\n') + (not b)
			pointer = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(pointer))
		self.nl -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class iow(IOBase):

	def __init__(self, file):
		self.buffer = fio(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda x: self.buffer.write(x.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (iow(sys.stdin), iow(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict
mod = 10 ** 9 + 7
(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
cnt = defaultdict(lambda : 0)
dp = [[0 for j in range(k + 1)] for i in range(n + 2)]
for i in range(1, n + 1):
	dp[i][0] = 1
for j in range(1, k + 1):
	for i in range(1, n + 1):
		dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1]) % mod
for i in range(1, n + 1):
	for j in range(k + 1):
		cnt[i] += dp[i][j] * dp[i][k - j] % mod
ans = 0
for i in range(n):
	ans += cnt[i + 1] * a[i] % mod
for _ in range(q):
	(i, x) = map(int, input().split())
	ans = (ans + (x - a[i - 1]) * cnt[i]) % mod
	a[i - 1] = x
	sys.stdout.write(str(ans % mod) + '\n')


import sys
input = sys.stdin.buffer.readline
(n, k, q) = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
pcc = [1] * n * (k + 1)
for i in range(k):
	pcc[(i + 1) * n + 0] = pcc[i * n + 1]
	pcc[(i + 1) * n + n - 1] = pcc[i * n + n - 2]
	for p in range(1, n - 1):
		pcc[(i + 1) * n + p] = (pcc[i * n + p - 1] + pcc[i * n + p + 1]) % MOD
cc = [0] * n
for p in range(n):
	for i in range(k + 1):
		cc[p] = (cc[p] + pcc[i * n + p] * pcc[(k - i) * n + p]) % MOD
sm = 0
for p in range(n):
	sm = (sm + a[p] * cc[p]) % MOD
for _ in range(q):
	(p, x) = map(int, input().split())
	p -= 1
	sm = (sm + cc[p] * (x - a[p])) % MOD
	a[p] = x
	print(sm)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k, q) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
dp = [[0 for x in range(k + 1)] for x in range(n)]
mod = 10 ** 9 + 7
for i in range(n):
	dp[i][0] = 1
for left in range(1, k + 1):
	for i in range(n):
		if i > 0:
			dp[i][left] += dp[i - 1][left - 1]
		if i < n - 1:
			dp[i][left] += dp[i + 1][left - 1]
		dp[i][left] %= mod
coff = [0 for x in range(n)]
for i in range(n):
	for j in range(k + 1):
		coff[i] += dp[i][j] * dp[i][k - j]
		coff[i] %= mod
ans = 0
for j in range(n):
	ans += coff[j] * arr[j]
	ans %= mod
for i in range(q):
	(index, val) = [int(x) for x in input().split()]
	ans += coff[index - 1] * (val - arr[index - 1])
	ans %= mod
	sys.stdout.write(str(ans) + '\n')
	arr[index - 1] = val


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):

	def __init__(self, file):
		self.newlines = 0
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def S():
	return input().strip()

def print_list(l):
	print(' '.join(map(str, l)))
M = 10 ** 9 + 7
(n, k, q) = RL()
a = [0] + RLL() + [0]
count = [[0] * (n + 2) for _ in range(k + 1)]
count[0][1:-1] = [1] * n
for t in range(1, k + 1):
	for i in range(1, n + 1):
		count[t][i] = (count[t - 1][i - 1] + count[t - 1][i + 1]) % M
res = [0] * (n + 2)
for i in range(1, (n + 1) // 2 + 1):
	for j in range((k + 1) // 2):
		res[i] = (res[i] + count[j][i] * count[k - j][i] % M) % M
	res[i] = res[i] * 2 % M
	if k & 1 == 0:
		res[i] = (res[i] + count[k // 2][i] * count[k // 2][i] % M) % M
for i in range((n + 1) // 2 + 1, n + 1):
	res[i] = res[n + 1 - i]
s = 0
for i in range(1, n + 1):
	s = (s + a[i] * res[i] % M) % M
for _ in range(q):
	(i, x) = RL()
	s = (s + (x - a[i]) * res[i] % M) % M
	a[i] = x
	print(s)


import collections, functools
import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
(n, k, q) = map(int, sys.stdin.readline().split())
arr = list(map(int, input().split()))
s = collections.Counter()
mid = (n + 1) // 2
dp = [[0 for i in range(mid)] for j in range(k + 1)]
for i in range(mid):
	dp[0][i] = 1
for j in range(1, k + 1):
	for i in range(mid):
		if i + 1 < mid:
			dp[j][i] += dp[j - 1][i + 1]
		elif mid % 2:
			dp[j][i] += dp[j - 1][i - 1]
		else:
			dp[j][i] += dp[j - 1][i]
		if i - 1 >= 0:
			dp[j][i] += dp[j - 1][i - 1]
		dp[j][i] %= mod
for i in range(mid):
	for j in range((k + 1) // 2):
		s[i] += 2 * dp[k - j][i] * dp[j][i]
	if k % 2 == 0:
		s[i] += dp[k // 2][i] ** 2
	s[i] %= mod
for i in range(mid, n):
	s[i] += s[n - 1 - i]
ans = 0
for i in s:
	ans += arr[i] * s[i]
ans = ans % mod
for i in range(q):
	(ind, val) = map(int, input().strip().split())
	ans += (val - arr[ind - 1]) * s[ind - 1]
	arr[ind - 1] = val
	ans = ans % mod
	print(ans)


import sys, io, os

class DSumOfPaths:

	def solve(self, tc=0):
		MOD = 10 ** 9 + 7
		(n, k, Q) = [int(_) for _ in input().split()]
		a = [int(_) for _ in input().split()]
		cnt = [0] * n
		dp = [[0] * (n + 1) for _ in range(k + 1)]
		dp[0] = [1] * (n + 1)
		for u in range(1, k + 1):
			dp[u][0] = dp[u - 1][1]
			dp[u][n - 1] = dp[u - 1][n - 2]
			for i in range(1, n - 1):
				dp[u][i] = (dp[u - 1][i + 1] + dp[u - 1][i - 1]) % MOD
		for index in range(n):
			for p in range(k + 1):
				q = k - p
				cnt[index] += dp[p][index] * dp[q][index]
				cnt[index] %= MOD
		sm = 0
		for i in range(n):
			sm += cnt[i] * a[i]
			sm %= MOD
		ans = [0] * Q
		queries = []
		for _ in range(Q):
			queries.append([int(_) for _ in input().split()])
		for qi in range(Q):
			(i, x) = queries[qi]
			sm -= cnt[i - 1] * a[i - 1]
			a[i - 1] = x
			sm += cnt[i - 1] * a[i - 1]
			sm %= MOD
			ans[qi] = str(sm)
		print('\n'.join(ans))
solver = DSumOfPaths()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
solver.solve()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k, q) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0 for j in range((n + 1) // 2)] for i in range(k // 2 + 1)]
dp[0] = [1 for j in range((n + 1) // 2)]
for i in range(1, k // 2 + 1):
	for j in range((n + 1) // 2):
		if j:
			dp[i][j] += dp[i - 1][j - 1]
			dp[i][j] %= mod
		if j != (n + 1) // 2 - 1:
			dp[i][j] += dp[i - 1][j + 1]
			dp[i][j] %= mod
	if n % 2 == 1:
		dp[i][(n + 1) // 2 - 1] += dp[i - 1][(n + 1) // 2 - 2]
		dp[i][(n + 1) // 2 - 1] %= mod
	else:
		dp[i][(n + 1) // 2 - 1] += dp[i - 1][(n + 1) // 2 - 1]
		dp[i][(n + 1) // 2 - 1] %= mod
cnt = [0 for i in range((n + 1) // 2)]
if k % 2 == 0:
	for i in range((n + 1) // 2):
		cnt[i] += dp[k // 2][i] * dp[k // 2][i]
		cnt[i] %= mod
sub = [dp[-1][j] for j in range((n + 1) // 2)]
for i in range(k // 2 + 1, k + 1):
	next = [0 for j in range((n + 1) // 2)]
	for j in range((n + 1) // 2):
		if j:
			next[j] += sub[j - 1]
			next[j] %= mod
		if j != (n + 1) // 2 - 1:
			next[j] += sub[j + 1]
			next[j] %= mod
	if n % 2 == 1:
		next[(n + 1) // 2 - 1] += sub[(n + 1) // 2 - 2]
		next[(n + 1) // 2 - 1] %= mod
	else:
		next[(n + 1) // 2 - 1] += sub[(n + 1) // 2 - 1]
		next[(n + 1) // 2 - 1] %= mod
	for j in range((n + 1) // 2):
		cnt[j] += 2 * next[j] * dp[k - i][j]
		cnt[j] %= mod
	sub = next
cnt += [cnt[-2 - j] for j in range(n // 2)] if n % 2 == 1 else [cnt[-1 - j] for j in range(n // 2)]
a = list(map(int, input().split()))
res = 0
ans = []
for i in range(n):
	res += a[i] * cnt[i]
	res %= mod
for i in range(q):
	(idx, x) = map(int, input().split())
	idx -= 1
	res = res + cnt[idx] * (x - a[idx])
	res %= mod
	a[idx] = x
	ans.append(res)
print(*ans, sep='\n')


import sys
sys.setrecursionlimit(10 ** 5)
p2D = lambda x: print(*x, sep='\n')

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))
inf = 10 ** 16
md = 10 ** 9 + 7
(n, k, q) = MI()
aa = LI()
dp = [[1] * n for _ in range(k + 1)]
for i in range(k):
	for j in range(n):
		if j == 0:
			dp[i + 1][j] = dp[i][j + 1]
		elif j == n - 1:
			dp[i + 1][j] = dp[i][j - 1]
		else:
			dp[i + 1][j] = (dp[i][j - 1] + dp[i][j + 1]) % md
ss = []
for j in range(n):
	cur = 0
	for i in range(k + 1):
		cur += dp[i][j] * dp[k - i][j]
	cur %= md
	ss.append(cur)
ans = sum((a * c % md for (a, c) in zip(aa, ss))) % md
for _ in range(q):
	(i, x) = MI()
	i -= 1
	ans = (ans + (x - aa[i]) * ss[i]) % md
	aa[i] = x
	print(ans)


from sys import stdin
import sys
mod = 10 ** 9 + 7
tt = 1
ans = []
for loop in range(tt):
	(n, k, q) = map(int, stdin.readline().split())
	dp = [[0] * (k + 1) for i in range(n)]
	for j in range(k, -1, -1):
		for i in range(n):
			if j == k:
				dp[i][j] = 1
				continue
			if i != 0:
				dp[i][j] += dp[i - 1][j + 1]
			if i != n - 1:
				dp[i][j] += dp[i + 1][j + 1]
			dp[i][j] %= mod
	slis = [0] * n
	for i in range(n):
		for j in range(k + 1):
			slis[i] += dp[i][j] * dp[i][k - j]
		slis[i] %= mod
	nsum = 0
	a = list(map(int, stdin.readline().split()))
	for i in range(n):
		nsum += slis[i] * a[i]
	nsum %= mod
	for i in range(q):
		(ind, x) = map(int, stdin.readline().split())
		ind -= 1
		nsum += slis[ind] * (x - a[ind])
		a[ind] = x
		nsum %= mod
		ans.append(nsum)
print('\n'.join(map(str, ans)))


from functools import cmp_to_key
from collections import deque, Counter
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def si():
	return str(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def lsi():
	return list(map(str, inp().split()))

def print_list(lista, space=' ', **kwargs):
	print(space.join(map(str, lista)), **kwargs)

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)
MOD = 10 ** 9 + 7
maxN = 5
FACT = [0] * maxN
INV_FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def inverseFactorials():
	n = len(INV_FACT)
	INV_FACT[n - 1] = inverse(FACT[n - 1])
	for i in range(n - 2, -1, -1):
		INV_FACT[i] = multiply(INV_FACT[i + 1], i + 1)

def coeffBinom(n, k):
	if n < k:
		return 0
	return multiply(FACT[n], multiply(INV_FACT[k], INV_FACT[n - k]))

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path
(n, k, q) = li()
a = li()
dp = [[0 for _ in range(k + 1)] for _ in range(n)]
for i in range(n):
	dp[i][0] = 1
for j in range(1, k + 1):
	dp[0][j] = dp[1][j - 1]
	dp[n - 1][j] = dp[n - 2][j - 1]
	for i in range(1, n - 1):
		dp[i][j] = add(dp[i + 1][j - 1], dp[i - 1][j - 1])
mosse = []
for i in range(n):
	m = 0
	for j in range(k + 1):
		m = add(m, multiply(dp[i][j], dp[i][k - j]))
	mosse.append(m)
somme = 0
for i in range(n):
	somme = add(somme, multiply(a[i], mosse[i]))
for p in range(q):
	(i, ai) = li()
	i -= 1
	diff = ai - a[i]
	a[i] = ai
	diff = multiply(diff, mosse[i])
	somme = add(somme, diff)
	print(somme)


import sys, io, os
read = sys.stdin.readline
input = lambda : map(int, read().split())
M = 10 ** 9 + 7
(n, k, q) = input()
a = list(input())
r = [0] * (n * (k + 1))
for i in range(n):
	r[i] = 1
for j in range(1, k + 1):
	for i in range(1, n - 1):
		r[j * n + i] = r[(j - 1) * n + i - 1] + r[(j - 1) * n + i + 1]
		if r[j * n + i] > M:
			r[j * n + i] -= M
	r[j * n] = r[(j - 1) * n + 1]
	r[j * n + n - 1] = r[(j - 1) * n + n - 2]
s = [0] * n
for i in range(n):
	for j in range(k + 1):
		s[i] = (s[i] + r[j * n + i] * r[(k - j) * n + i]) % M
v = 0
for i in range(n):
	v = (v + s[i] * a[i]) % M
out = []
for _ in range(q):
	(i, x) = input()
	v = (v + (x - a[i - 1]) * s[i - 1]) % M
	a[i - 1] = x
	out.append(str(v))
print('\n'.join(out))


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k, q) = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
X = [[1] * n for i in range(k + 1)]
for i in range(1, k + 1):
	for j in range(n):
		if j == 0:
			X[i][0] = X[i - 1][1]
		elif j == n - 1:
			X[i][j] = X[i - 1][j - 1]
		else:
			X[i][j] = (X[i - 1][j - 1] + X[i - 1][j + 1]) % mod
ANS = [0] * n
for j in range(n):
	for i in range(k + 1):
		ANS[j] = (ANS[j] + X[i][j] * X[k - i][j]) % mod
X = 0
for i in range(n):
	X = (X + ANS[i] * A[i]) % mod
AA = []
for tests in range(q):
	(a, x) = map(int, input().split())
	a -= 1
	X = (X + ANS[a] * (x - A[a])) % mod
	A[a] = x
	AA.append(X)
sys.stdout.write(str('\n'.join(map(str, AA))))


import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 1000000007
(n, k, q) = map(int, input().split())
dp = [[0 for j in range(k + 1)] for i in range(n + 1)]
for i in range(n):
	dp[i][0] = 1
for j in range(1, k + 1):
	dp[0][j] = dp[1][j - 1]
	for i in range(1, n - 1):
		dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1]) % mod
	dp[n - 1][j] = dp[n - 2][j - 1]
count = [0] * n
for i in range(n):
	for j in range(k + 1):
		count[i] += dp[i][j] * dp[i][k - j]
		count[i] %= mod
a = list(map(int, input().split()))
ans = 0
for i in range(n):
	ans += a[i] * count[i]
	ans %= mod
for _ in range(q):
	(i, x) = map(int, input().split())
	i -= 1
	ans -= a[i] * count[i]
	ans += mod
	ans %= mod
	ans += x * count[i]
	ans %= mod
	a[i] = x
	print(ans)