Description

你需要求出满足如下条件的长度为 $m$ 的序列 $B$ 的个数：

• $B$ 中全为正整数。
• $B$ 中不包含 $x$。
• $B$ 中元素两两不同。
• $B$ 中元素在范围 $[1,n]$ 中。
• $B$ 中任意两个元素相差不会超过 $t$。

$q$ 次询问，每次给出 $x$ 和 $t$。

由于结果可能很大，输出答案对 $10^9+7$ 取余的结果。

Input Format

本题输入均为正整数。

第一行三个数 $n,m,q$。

接下来 $q$ 行，每行两个数 $x,t$ 代表一个询问。

Output Format

输出 $q$ 行，每行一个数，第 $i$ 行代表第 $i$ 次询问的答案对 $10^9+7$ 取余的结果。

6 3 3
1 3
2 3
3 5

42
30
60

10 7 5
3 9
8 6
5 7
9 6
10 7

181440
5040
15120
10080
75600

Hint

数据范围

本题采用捆绑测试。

• Subtask 1（10 points）：$n \le 12$，$m\le 7$，$q\le 10$。
• Subtask 2（15 points）：$n \le 2000$，$m=2$，$q\le 2000$。
• Subtask 3（15 points）：$m=2$。
• Subtask 4（20 points）：$x\le t$。
• Subtask 5（40 points）：无特殊限制。

对于所有测试数据，$2\le n \le 2 \times 10 ^5$，$2 \le m \le n$，$1 \le x \le n$，$m - 1\le t < n$，$1 \le q \le 2\times 10^5$。