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:
//"Hello there
#define _CRT_SECURE_NO_WARNINGS
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <iomanip>
#include <fstream>
#include <queue>
#include <random>
#include <streambuf>
#include <sstream>
#include <cstdlib>
#include <chrono>
#include <bitset>
#include <numeric>
#include <unordered_map>


using namespace std;
using ll = int64_t; 
using vl = vector<ll>; 
using pll = pair<ll, ll>;

ll mod = 1000000007;
mt19937_64 rng(0xDEADBEEF);
string alpha = []() {string ans; for (char c = 'a'; c <= 'z'; c++)ans.push_back(c); return ans; }();


#define fLetter(L,N) for(ll L=0,L ## end=ll(N);L<L ## end;L++)
#define fi(N) fLetter(i,N)
#define fj(N) fLetter(j,N)
#define fk(N) fLetter(k,N)

#define f1(N) for(auto&i1:N)
#define f2(N) for(auto&i2:N)
#define f3(N) for(auto&i3:N)
#define all(N) N.begin(),N.end()




#define f12(A,B) if (auto it2 = B.begin(); true)f1(A)if (it2 == B.end())break; else if (auto&i2 = *it2++; true)
#define f13(A,B) if (auto it3 = B.begin(); true)f1(A)if (it3 == B.end())break; else if (auto&i3 = *it3++; true)
#define f23(A,B) if (auto it3 = B.begin(); true)f2(A)if (it3 == B.end())break; else if (auto&i3 = *it3++; true)
#define f123(A,B,C) if (auto it2 = B.begin(); true)if (auto it3 = C.begin(); true)f1(A)if (it2 == B.end() || it3 == C.end())break; else if (auto&i2 = *it2++; true)if (auto&i3 = *it3++; true)








#define tp1 typename T1
#define tp2 typename T2
#define tp3 typename T3
#define TP1 template<tp1>
#define TP2 template<tp1, tp2>
#define TP3 template<tp1, tp2, tp3>
#define o operator


TP1 istream& o>>(istream&c, vector<T1>& v) { f1(v)c >> i1; return c; }
TP2 istream& o>>(istream&c, pair<T1, T2>& p) { c >> p.first >> p.second; return c; }
TP2 ostream& o<<(ostream&c, pair<T1, T2> p) { return c << p.first << ' ' << p.second; }
TP1 ostream& o<<(ostream&c, const vector<T1>&v) { f1(v)c << i1 << ' '; return c; }
TP1 ostream& o << (ostream&c, const set<T1>&v) { f1(v)c << i1 << ' '; return c; }
TP1 void print(const vector<T1>&v) { f1(v)cout << i1 << endl; }

#ifdef CF_LOCAL
auto startProgExec = std::chrono::high_resolution_clock::now();
void myTiming()
{
	cout << endl << "Time elapsed : ";
	cout << chrono::duration<double, std::milli>(std::chrono::high_resolution_clock::now() - startProgExec).count() / 1000.0;
}
#endif 


class TIn {}; const TIn vIn; TP1 struct TInContainer { T1 Value; };
TP1 TInContainer<T1> o>>(const T1&value, const TIn vIn) { return { value }; }
TP1 bool o>>(const TInContainer<T1>&e, const set<T1>&v) { return v.find(e.Value) != v.end(); }
TP1 bool o>> (const TInContainer<T1>&e, const vector<T1>&v) { return find(v.begin(), v.end(), e.Value) != v.end(); }
TP1 bool o>> (const TInContainer<T1>&e, const multiset<T1>&v) { return v.find(e.Value) != v.end(); }
TP2 bool o>>(const TInContainer<T1>&e, const map<T1, T2>&v) { return v.find(e.Value) != v.end(); }
TP2 bool o>> (const TInContainer<T1>&e, const multimap<T1, T2>&v) { return v.find(e.Value) != v.end(); }
TP1 bool o>> (const TInContainer<T1>&e, const pair<T1, T1>&v) { return !(e.Value < v.first || v.second < e.Value); }
#define in >>vIn>>


TP1 ll o + (const vector<T1>&v) { return v.size(); }
TP1 ll o + (const set<T1>&v) { return v.size(); }
TP1 ll o + (const multiset<T1>&v) { return v.size(); }
TP2 ll o + (const map<T1,T2>&v) { return v.size(); }
TP2 ll o + (const multimap<T1, T2>&v) { return v.size(); }
TP1 ll o + (const queue<T1>&v) { return v.size(); }
TP1 ll o + (const priority_queue<T1>&v) { return v.size(); }
ll o + (const string&v) { return v.size(); }

TP1 vector<T1> o + (vector<T1> v1, const vector<T1>&v2) { for (auto&i1 : v2)v1.push_back(i1); return v1; }

TP2 void o+=(set<T1>&c, const T2&v) { c.insert(v); }
TP2 void o+=(multiset<T1>&c, const T2&v) { c.insert(v); }
TP3 void o+= (multimap<T1,T2>&c, const T3&v) { c.insert(v); }
TP2 void o+=(vector<T1>&c, const T2&v) { c.push_back(v); }
TP2 void o+=(queue<T1>&c, const T2&v) { c.push(v); }
TP2 void o+=(priority_queue<T1>&c, const T2&v) { c.push(v); }

TP2 void o-=(set<T1>&c, const T2&v) { c.erase(v); }
TP2 void o-=(multiset<T1>&c, const T2&v) { c.erase(c.find(v)); }
TP3 void o-=(map<T1, T2>&c, const T3&v) { c.erase(v); }
TP3 void o-= (multimap<T1, T2>&c, const T3&v) { c.erase(c.find(v)); }

TP1 T1 o--(set<T1>&c) { T1 ans = *c.begin(); c.erase(c.begin()); return ans; }
TP1 T1 o--(multiset<T1>&c) { T1 ans = *c.begin(); c.erase(c.begin()); return ans; }
TP1 T1 o--(vector<T1>&c) { T1 ans = c.back(); c.pop_back(); return ans; }
char o--(string&c) { char ans = c.back(); c.pop_back(); return ans; }
TP1 T1 o--(queue<T1>&c) { T1 ans = c.front(); c.pop(); return ans; }
TP1 T1 o--(priority_queue<T1>&c) { T1 ans = c.top(); c.pop(); return ans; }

TP2 ll o/(const T1&v, const T2&c) { return count(c.begin(), c.end(), v); }

TP2 void o^=(set<T1>&c, const T2&v)
{
	if (c.find(v) != c.end())c.erase(v);
	else c.insert(v);
}




TP1 void o<<=(map<T1, ll>&m, const vector<T1>&v) { for (auto&i1 : v)m[i1]++; }
void o <<= (map<char, ll>&m, const string&v) { for (auto&i1 : v)m[i1]++; }
TP2 void o<<=(map<T1, T2>&m, const vector<pair<T1, T2>>&v) { for (auto&i1 : v)m[i1.first] = i1.second; }
TP1 void o<<=(set<T1>&s, const vector<T1>&v) { for (auto&i1 : v)s.insert(i1); }
TP1 void o <<= (multiset<T1>&s, const vector<T1>&v) { for (auto&i1 : v)s.insert(i1); }
void o <<= (set<char>&s, const string&v) { for (auto&i1 : v)s.insert(i1); }




TP1 T1 sum(const vector<T1>&v) { return accumulate(v.begin(), v.end(), T1{}); }
TP1 T1 max(const vector<T1>&v) { return *max_element(v.begin(), v.end()); }
TP1 T1 min(const vector<T1>&v) { return *min_element(v.begin(), v.end()); }
TP1 void sort(vector<T1>&v) { sort(v.begin(), v.end()); }
TP1 void reverse(vector<T1>&v) { reverse(v.begin(), v.end()); }
void reverse(string&a) { reverse(a.begin(), a.end()); }
void sort(string&a) { sort(a.begin(), a.end()); }
TP1 vector<T1> sorted(vector<T1> v) { sort(v.begin(), v.end()); return move(v); }
TP1 vector<T1> reversed(vector<T1> v) { reverse(v.begin(), v.end()); return move(v); }
string reversed(string a) { reverse(a.begin(), a.end()); return move(a); }
string sorted(string a) { sort(a.begin(), a.end()); return move(a); }
TP1 T1 max(const pair<T1, T1>&v) { return max(v.first, v.second); }
TP1 T1 min(const pair<T1, T1>&v) { return min(v.first, v.second); }
TP1 void sort(pair<T1, T1>&v) { if (v.second < v.first)swap(v.first, v.second); }
TP1 pair<T1, T1> sorted(pair<T1, T1> v) { if (v.second < v.first)swap(v.first, v.second); return move(v); }
TP2 vector<pair<T2, T1>> swapped(const map<T1, T2>&mp) { vector<pair<T2, T1>> ans; f1(mp)ans.push_back({ i1.second,i1.first }); return move(ans); }


namespace geom
{
	pll o+(pll a, pll b) { return { a.first + b.first,a.second + b.second }; }
	pll o-(pll a, pll b) { return { a.first - b.first,a.second - b.second }; }
	pll o-(pll a) { return { -a.first,-a.second }; }
	pll o*(pll a) { return { -a.second,a.first }; }
	pll o~(pll a) { return { a.second,a.first }; }
	pll o++(pll&a) { pll ans = a; a.first++; a.second++; return ans; }
	pll o--(pll&a) { pll ans = a; a.first--; a.second--; return ans; }
	ll o*(pll a, pll b) { return a.first * b.first + a.second * b.second; }
	ll o+(pll a) { return a.first*a.first + a.second*a.second; }
	ll abs(pll a) { return std::abs(a.first) + std::abs(a.second); }
	pll sum(const vector<pll>&v) { using namespace geom; pll ans{}; for (auto e : v)ans = ans + e; return ans; }
	void o+= (pll&a, pll b) { a = a + b; }
	void o-= (pll&a, pll b) { a = a - b; }
	pll o*(ll a, pll p) { return { p.first*a, p.second*a }; }
	void o *= (pll p, ll a) { p.first *= a; p.second *= a; }
}

using vpll = vector<pll>;
using mll = map<ll, ll>;
using vvl = vector<vl>;
using vs = vector<string>; 
using md = double;
TP1 class asc_queue : public priority_queue<T1, vector<T1>, greater<T1>> {};
TP1 class desc_queue : public priority_queue<T1> {};





TP1 string tostring(T1 a)
{
	stringstream ss;
	ss << a;
	return ss.str();
}

vector<string> split(std::string_view line, set<char> delim) {
	vector<string> out;
	out.emplace_back();
	for (auto c : line) {
		if (c in delim)
			out.emplace_back();
		else
			out.back().push_back(c);
	}
	return out;
}

namespace algo
{
	TP1 T1 binpow_mod(T1 a, ll b, ll c = mod)
	{
		if (b == 1)return a;
		if (b & 1)return binpow_mod(a, b - 1, c)*a%c;
		T1 res = binpow_mod(a, b >> 1, c);
		return res * res%c;
	}
	TP1 T1 binpow(T1 a, ll b)
	{
		if (b == 1)return a;
		if (b & 1)return binpow(a, b - 1)*a;
		T1 res = binpow(a, b >> 1);
		return res * res;
	}
	class dsu
	{
		vl v;
		ll Sz;
	public:
		dsu(ll sz) :v(sz), Sz(sz) { fi(sz)v[i] = i; }
		ll get(ll i)
		{
			if (i == v[i])return v[i];
			return v[i] = get(v[i]);
		}
		ll o[](ll i) { return get(i); }
		void join(ll a, ll b)
		{
			if (get(a) == get(b)) return;
			Sz--;
			if (rng() % 2)swap(a, b);
			v[get(a)] = get(b);
		}
		ll size() const { return Sz; }
	};

	ll gcd(ll a, ll b) { while (a)tie(a, b) = pll{ b%a,a }; return b; }
	ll gcdv(vl&v) { return accumulate(all(v), v.front(), gcd); }

	union mask_t
	{
		uint64_t i;
		bitset<64> b;
		mask_t(ll q) { i = q; }
		mask_t(bitset<64> q) { b = q; }
	};

	vector<bool> eratosphen(ll mx)
	{
		if (mx == 0)return {1};
		vector<bool> ans(mx + 1);
		ans[0] = 1;
		ans[1] = 1;
		for (ll i = 2; i <= mx; i++)
		{
			if (ans[i])continue;
			for (ll j = i + i; j <= mx; j += i)
				ans[j] = 1;
		}
		return ans;
	}
	vl primes(ll n)
	{
		auto v = eratosphen(n);
		vl ans;
		fi(v.size())if (!v[i])ans += i;
		return ans;
	}

	mll primes_to_pow(ll n) 
	{
		mll ans;
		for (ll i = 2; i*i <= n; i++) {
			while (n%i == 0) {
				ans[i]++;
				n /= i;
			}
		}
		if (n != 1)ans[n]++;
		return ans;
	}

	TP1 vector<T1> prefixsum(vector<T1> v)
	{
		vector<T1> ans(1);
		f1(v)ans += ans.back() + i1;
		return move(ans);
	}
	TP1 vector<T1> suffixsum(vector<T1> v)
	{
		return reversed(prefixsum(reversed(v)));
	}
	
	

	TP1 T1 merge(const T1&a, const T1&b)
	{
		T1 ans(a.size() + b.size());
		merge(a.begin(), a.end(), b.begin(), b.end(), ans.begin());
		return move(ans);
	}

	/*TP1 ll ternary_int_max(ll l, ll r, T1(*func)(ll))
	{
		if (r - l < 10)
		{
			vector<T1> ans;
			for (ll i = l; i < r; i++)ans += func(i);
			return max(ans);
		}

	}*/

	pll exgcd(pll a)
	{
		if (a.first == 0)
		{
			if (a.second == 1)return { 0,1 };
			else return { 0,0 };
		}
		pll val = exgcd({ a.second%a.first, a.first });
		
		
		
		
		
		
		return { val.second - (a.second / a.first)*val.first, val.first };
	}

	TP1 vl kmp(T1&v)
	{
		vl ans(+v);
		ll j = 0;
		fi(+v)
		{
			while (j != 0 && v[i] != v[j])
				j = ans[j - 1];
			if (v[j] == v[i] && j < i)
				j++;
			ans[i] = j;
		}
		return ans;
	}

	/*TP2 class make_dp {
		using func_type = T2(*)(T1);
		func_type func;
		map<T1, T2> dp;
	public:
		make_dp(func_type _func) : func(_func) {}
		T2 operator()(T1 arg) {
			if (arg in dp) {
				return dp[arg];
			}
			return dp[arg] = func(arg);
		}
	};*/
}

#undef tp1
#undef tp2
#undef tp3
#undef TP1
#undef TP2
#undef TP3
#undef o

//#include "kaggle.h"
class context {
public:
	
};

int main() {
#ifdef CF_LOCAL
	freopen("C:\\progs\\cpp\\vs\\cf\\input.txt", "r", stdin);
	//freopen("C:\\progs\\cpp\\vs\\cf\\output.txt", "w", stdout);
	startProgExec = chrono::high_resolution_clock::now();
	atexit(myTiming);
#endif 
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.sync_with_stdio(0);
	cout.tie(0);

	using namespace geom;

	
	

  
	ll n, k, q; cin >> n >> k >> q;
	vl a(n); cin >> a;
	vl v(n); f1(v)i1 = 1;
	vector<vl> vlen(k + 1, vl(n));
	vlen[0] = v;
	
	fj(k) {
		vl vnext(n);
		vnext[0] = v[1];
		vnext[n - 1] = v[n - 2];
		for (ll i = 1; i < n - 1; i++) {
			vnext[i] = v[i - 1] + v[i + 1];
		}
		f1(vnext)i1 %= mod;
		v = vnext;
		fi(n)vlen[j+1][i] += v[i];
		
	}
	vl vsm(n);
	fi(n) {
		fj(k + 1) {
			vsm[i] += vlen[j][i] * vlen[k - j][i];
			vsm[i] = vsm[i] % mod;
		}
	}
	
	ll ans = 0;
	fi(n) {
		ans += vsm[i] * a[i];
		ans %= mod;
	}
	fj(q) {
		ll idx, x; cin >> idx >> x;
		idx--;
		ans = (mod * mod + ans + (x - a[idx]) * vsm[idx]) % mod;
		a[idx] = x;
		cout << ans << endl;
	}

	return 0;
}