高橋商店では \(N\) 種類の商品が売られています。「どの種類の商品がいくつあるか」の情報が与えられるので、「合計 \(M\) 個の商品を選ぶ方法」の数を求めて下さい。ただし、同じ種類の商品は区別しないこととします。
いや、これは少し簡単過ぎるので、ちょっとした注文も追加しよう。整数 k, x からなる \(Q\) 個の注文を用意したので、それぞれについて「\(k_i\) 種類目の商品をちょうど \(x_i\) 個選ばなければならないとき、合計 \(M\) 個の商品を選ぶ方法」の数を求めて下さい。

高桥商店出售 \(N\) 种类型的商品。 给出 "有多少种产品可供选择 "的信息，找出 "选择总共M种产品的方法 "的数量。 然而，我们将不对同一类型的产品进行区分。
不，这有点太容易了，所以让我们增加一个小订单。 我们有 \(Q\) 个由整数 \(k\) 和 \(x\) 组成的订单。对于每一个订单，请找出 "当正好要选择第 \(k_i\) 种产品的 \(x_i\) 个产品时，总共要选择 \(M\) 个产品的方法 "的数目。

商品的种类个数：\(a_i\)，\(k_i\le M\)，\(x_i\le a_{x_i}\)。

• \(10\%\) 的数据，\(N,M,Q \le 100\)

• \(30\%\) 的数据，\(N,M\le 100,Q\le 5\cdot 10^5\)

• \(80\%\) 的数据，\(N,M\le 2000,Q\le 1000\)

• \(100\%\) 的数据，\(N,M\le 2000,Q\le 5\cdot 10^5\)

#include <bits/stdc++.h>

using namespace std;

#define dg(x) cout<<#x<<"="<<x<<endl

using ll = long long;

const int N = 2e3+3;
const int mod = 1e9+7;

ll n,m,q,a[N];
ll dp[N][N],ans[N][N],pre[N];

ll cal(int i){
	if (i<0){
		return 0;
	}
	return pre[i];
}

void precalc(){
	dp[0][0]=1;
	for (int i=0; i<=m; i++){
		pre[i]=1;
	}
	for (int i=1; i<=n; i++){
		for (int j=0; j<=m; j++){
			dp[i][j]=pre[j]-cal(j-a[i]-1);
			dp[i][j]=(dp[i][j]+mod)%mod;
		}
		pre[0]=dp[i][0];
		for (int j=1; j<=m; j++){
			pre[j]=pre[j-1]+dp[i][j];
			pre[j]%=mod;
		}
	}
}

void anscalc(){
	for (int i=1; i<=n; i++){
		for (int j=0; j<=m; j++){
			pre[j]=0;
		}
		ans[i][0]=pre[0]=1;
		for (int j=1; j<=m; j++){
			ll interval_sum=(pre[j-1]-cal(j-a[i]-1)+mod)%mod;
			ans[i][j]=(dp[n][j]-interval_sum+mod)%mod;
			pre[j]=pre[j-1]+ans[i][j];
			pre[j]%=mod;
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>m>>q;
	for (int i=1; i<=n; i++){
		cin>>a[i];
	}
	precalc();
	anscalc();
	while (q--){
		int k,x;
		cin>>k>>x;
		cout<<ans[k][m-x]<<endl;
	}
	return 0;
}