AT_arc028_4.[ARC028D] 注文の多い高橋商店

高桥商店有 $N$ 种商品。现给出每种商品的数量信息，请你求出“选出总共 $M$ 个商品的方法数”。注意，同一种商品之间不作区分。

不过，这样似乎有点太简单了，所以再加上一些小要求。现有 $Q$ 个订单，每个订单由整数 $k$ 和 $x$ 组成。对于每个订单，请你求出“必须恰好选出 $k_i$ 种商品中的第 $k_i$ 种商品 $x_i$ 个，且总共选出 $M$ 个商品的方法数”。

由于约束条件有误，已修正如下：$1\leq Q\leq 100,000$ → $1\leq Q\leq 500,000$（22:15）

输入通过标准输入给出，格式如下：

$N$ $M$ $Q$ $a_1$ $a_2$ … $a_N$
$k_1$ $x_1$
$k_2$ $x_2$
⋮
$k_Q$ $x_Q$

• 第 $1$ 行包含三个整数，分别表示商品种类数 $N\ (1\leq N\leq 2000)$，要选出的商品总数 $M\ (1\leq M\leq 2000)$，订单数 $Q\ (1\leq Q\leq 500,000)$，以空格分隔。
• 第 $2$ 行包含 $N$ 个空格分隔的整数，表示每种商品的数量信息。其中第 $i$ 个数 $a_i\ (1\leq a_i\leq M)$ 表示第 $i$ 种商品的数量。
• 第 $3$ 行到第 $Q+2$ 行，每行包含两个整数 $k_i\ (1\leq k_i\leq N)$ 和 $x_i\ (1\leq x_i\leq a_{k_i})$，以空格分隔。表示第 $i$ 个订单要求“必须恰好选出第 $k_i$ 种商品 $x_i$ 个，且总共选出 $M$ 个商品的方法数”。

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个订单的答案，对 $1,000,000,007\ (10^9+7)$ 取模。

部分分

本题设有部分分。

• 若能通过所有满足 $N\leq 100,\ M\leq 100,\ Q\leq 100$ 的测试点，可得 $10$ 分。
• 若能通过所有满足 $N\leq 100,\ M\leq 100$ 的测试点，可再得 $20$ 分。
• 若能通过所有满足 $Q\leq 1000$ 的测试点，可再得 $50$ 分。

样例说明 1

第 $1$ 个订单要求“必须恰好选出第 $1$ 种商品 $3$ 个，且总共选出 $5$ 个商品的方法数”，这样的选法有以下 $3$ 种：

• 第 $1$ 种商品选 $3$ 个，第 $2$ 种商品选 $2$ 个，第 $3$ 种商品选 $0$ 个。
• 第 $1$ 种商品选 $3$ 个，第 $2$ 种商品选 $1$ 个，第 $3$ 种商品选 $1$ 个。
• 第 $1$ 种商品选 $3$ 个，第 $2$ 种商品选 $0$ 个，第 $3$ 种商品选 $2$ 个。

第 $2$ 个订单要求从第 $2$ 种和第 $3$ 种商品中总共选出 $5$ 个商品，但商品数量不足，因此没有可行方案，应输出 $0$。

由 ChatGPT 4.1 翻译