Problem Description

Takahashi Store sells $ N $ types of products. Given information about "how many items of each type of product are available," please find the number of ways to choose a total of $ M $ items, considering that items of the same type are not distinguished.

However, this is a bit too simple, so let's add a little twist. We have prepared $ Q $ orders consisting of integers $ k $ and $ x $, and for each order, please find the number of ways to choose a total of $ M $ items when exactly $ x_i $ items of the $ k_i $-th type must be chosen.

Input Format

The constraints were incorrect, so they have been corrected. $1 \leq Q \leq 100,000$ → $1 \leq Q \leq 500,000$ (22:15)

The input is given from the standard input in the following format:

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

• The first line contains the number of product types $N\ (1 \leq N \leq 2000)$, the number of items to choose $M\ (1 \leq M \leq 2000)$, and the number of orders $Q\ (1 \leq Q \leq 500,000)$, separated by spaces.
• The second line contains $ N $ space-separated integers representing the number of items for each type of product. The $ i $-th integer $a_i\ (1 \leq a_i \leq M)$ represents the number of items for the $ i $-th type of product.
• The next $ Q $ lines contain information about the orders. The $ i $-th line contains two integers $k_i\ (1 \leq k_i \leq N)$ and $x_i\ (1 \leq x_i \leq a_{k_i})$, separated by spaces. This means that for the $ i $-th order, you must choose exactly $ x_i $ items of the $ k_i $-th type and find the number of ways to choose a total of $ M $ items.

Output Format

Output $ Q $ lines. The $ i $-th line should contain the answer to the $ i $-th order modulo $1,000,000,007\ (10^9+7)$.

Sample Input and Output

Sample Input #1

3 5 2
3 2 2
1 3
1 0

Sample Output #1

3
0

Sample Input #2

4 7 5
1 2 3 4
4 0
3 2
2 1
1 1
1 0

Sample Output #2

0
5
5
9
6

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve all test cases where $N \leq 100$, $M \leq 100$, and $Q \leq 100$, you will be awarded $ 10 $ points.
• If you correctly solve all test cases where $N \leq 100$ and $M \leq 100$, you will be awarded an additional $ 20 $ points.
• If you correctly solve all test cases where $Q \leq 1000$, you will be awarded an additional $ 50 $ points.

Sample Explanation 1

The first order is "When exactly $ 3 $ items of the $ 1 $-st type must be chosen, find the number of ways to choose a total of $ 5 $ items," and there are $ 3 $ such ways:
- Choose $ 3 $ items of the $ 1 $-st type, $ 2 $ items of the $ 2 $-nd type, and $ 0 $ items of the $ 3 $-rd type.
- Choose $ 3 $ items of the $ 1 $-st type, $ 1 $ item of the $ 2 $-nd type, and $ 1 $ item of the $ 3 $-rd type.
- Choose $ 3 $ items of the $ 1 $-st type, $ 0 $ items of the $ 2 $-nd type, and $ 2 $ items of the $ 3 $-rd type.

For the second order, you must choose a total of $ 5 $ items from the $ 2 $-nd and $ 3 $-rd types, but there are not enough items, so the answer is $ 0 $.

见题面 Input 部分

见题面 Output 部分