问题描述

在高桥商店里有N种商品。给出“每种商品有多少个”的信息，请计算“选取总共M个商品的方法数”。假设同一种商品无区别。

哦，这个似乎太简单了，我们来增加一些小要求。准备了Q个订单，每个订单由整数k和x组成，请计算以下内容：

对于每个订单i，计算“选取总共M个商品的方法数为ki种商品选择恰好xi个时”。

输入

修正了约束条件错误。改为1 ≦ Q ≦ 500,000（22:15）

从标准输入中以以下格式给出输入。

N M Q a1 a2 ... aN k1 x1 k2 x2 : kQ xQ

• 第1行包含3个整数，以空格分隔，分别表示商品种类数N（1 ≦ N ≦ 2000）、选取商品个数M（1 ≦ M ≦ 2000）和订单个数Q（1 ≦ Q ≦ 500,000）。
• 第2行按照空格分隔，给出每种商品的个数信息。其中第i个数字表示第i种商品的个数ai（1 ≦ ai ≦ M）。
• 从第3行到第Q+2行，给出与订单相关的信息。其中第i行包含两个整数，以空格分隔，表示ki（1 ≦ ki ≦ N）和xi（1 ≦ xi ≦ ai）。这表示第i个订单是“选取恰好xi个第ki种商品时，选取总共M个商品的方法数”。

部分分

该问题包括部分分。

• 对于满足N ≦ 100、M ≦ 100、Q ≦ 100的测试用例全部回答正确，得10分。
• 对于满足N ≦ 100、M ≦ 100的测试用例全部回答正确，额外得20分。
• 对于满足Q ≦ 1000的测试用例全部回答正确，额外得50分。

输出

请输出Q行结果。其中第i行输出第i个订单的答案，用1000000007（109+7）取模。

示例输入1

3 5 2
3 2 2
1 3
1 0

示例输出1

3
0

第一个订单是“选取恰好3个第1种商品时，选取总共5个商品的方法数”，有以下3种方法：

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

而第二个订单要求从第2种和第3种商品中选取总共5个商品，但是商品不够，所以不存在这样的方法，输出0。

示例输入2

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

示例输出2

0
5
5
9
6