#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXP = 4e6 + 5;
const int P    = 1e9 + 7;
typedef long long ll;

int inv[7];
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
struct SegmentTree {
	struct Node {
		int lc, rc;
		int ret[6], cnt[6];
	} a[MAXP];
	int size, n;
	void init(int x) {
		n = x;
	}
	void update(int root) {
		for (int i = 0; i < 6; i++) {
			a[root].cnt[i] = min(a[a[root].lc].cnt[i] + a[a[root].rc].cnt[i], P);
			a[root].ret[i] = (a[a[root].lc].ret[i] + a[a[root].rc].ret[i]) % P;
		}
	}
	int modify(int root, int l, int r, int pos, int v) {
		int ans = ++size;
		a[ans] = a[root];
		int tret = 1;
		int tcnt = 1;
		for (int i = 0; i < 6; i++) {
			a[ans].cnt[i] = min(a[ans].cnt[i] + tcnt, P);
			a[ans].ret[i] = (a[ans].ret[i] + tret) % P;
			tcnt = min(1ll * tcnt * (v + i) / (i + 1), (ll) P);
			tret = 1ll * tret * (v + i) % P * inv[i + 1] % P;
		}
		if (l == r) return ans;
		int mid = (l + r) / 2;
		if (mid >= pos) a[ans].lc = modify(a[ans].lc, l, mid, pos, v);
		else a[ans].rc = modify(a[ans].rc, mid + 1, r, pos, v);
		update(ans);
		return ans;
	}
	int modify(int root, int pos, int v) {
		return modify(root, 1, n, pos, v);
	}
	pair <int, int> query(int root, int l, int r, int k, int s) {
		if (l == r) return make_pair(l, 0);
		int mid = (l + r) / 2;
		if (a[a[root].lc].cnt[s] > k) return query(a[root].lc, l, mid, k, s);
		else {
			pair <int, int> tmp = query(a[root].rc, mid + 1, r, k - a[a[root].lc].cnt[s], s);
			tmp.second += a[a[root].lc].cnt[s];
			return tmp;
		}
	}
	pair <int, int> query(int root, int k, int s) {
		if (k >= a[root].cnt[s]) return make_pair(n + 1, a[root].cnt[s]);
		else return query(root, 1, n, k, s);
	}
	int conv[6];
	int sum(int root, int l, int r, int qr, int s) {
		if (qr >= r) {
			int ans = 0;
			for (int i = 0; i <= s; i++)
				ans = (ans + 1ll * conv[i] * a[root].ret[s - i]) % P;
			return ans;
		}
		if (l > qr) return 0;
		int mid = (l + r) / 2;
		return (sum(a[root].lc, l, mid, qr, s) + sum(a[root].rc, mid + 1, r, qr, s)) % P;
	}
	int sum(int root, int r, int x, int s) {
		if (r <= 0) return 0;
		int tmp = 1;
		for (int i = 0; i <= s; i++) {
			conv[i] = tmp;
			tmp = 1ll * tmp * (P - x - i) % P * inv[i + 1] % P;
		}
		return sum(root, 1, n, r, s);
	}
} ST;
int n, s, q, a[MAXN], p[MAXN], root[MAXN];
int query(int rt, int qr, int x, int s) {
	if (s == 0) return rt >= x && p[x] <= qr;
	else return ST.sum(root[rt], qr, x - 1, s - 1);
}
int main() {
	scanf("%d%d%d", &n, &s, &q);
	for (int i = 1; i <= s; i++)
		inv[i] = power(i, P - 2);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		p[a[i]] = i;
	}
	ST.init(n);
	for (int i = 1; i <= n; i++)
		root[i] = ST.modify(root[i - 1], p[i], i);
	for (int i = 1; i <= q; i++) {
		int k, x; scanf("%d%d", &x, &k);
		int rt = n, ans = 0;
		for (int j = s - 1; j >= 0; j--) {
			pair <int, int> tmp;
			tmp = ST.query(root[rt], k, j);
			ans = (ans + query(rt, tmp.first - 1, x, j)) % P;
			ans = (ans - query(x - 1, tmp.first - 1, x, j) + P) % P;
			if (tmp.first > n) break;
			else {
				rt = a[tmp.first];
				k -= tmp.second;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}