给定 $n$，$m$。有 $n$ 种商品，编号从 $1$ 到 $n$，第 $i$ 种商品最多能拿 $a_i$ 个。

共 $q$ 次询问。每次询问给定 $k$，$x$，求第 $k$ 种商品 恰好 拿走 $x$ 个的前提下，在 $n$ 种商品中一共拿走 $m$ 个商品的方案数。两种方案不同当且仅当存在一种商品在二方案中被拿走的个数不同。输出答案对 $10^9+7$ 取模的结果。

• $1 \leq n,m,a_i \leq 2\times 10^3$

• $1\leq k\leq n$

• $1\leq x\leq a_k$