Counting Constrained Sequences

You are given three integers n, m, and q. For each query, you are given two integers x and t. Your task is to count the number of sequences \(B\) of length \(m\) satisfying the following conditions:

• All elements of \(B\) are positive integers.
• The sequence \(B\) does not contain \(x\).
• All elements in \(B\) are pairwise distinct.
• Every element of \(B\) lies in the range \([1, n]\) (inclusive).
• The difference between any two elements does not exceed \(t\). In other words, if \(a\) and \(b\) are any two elements of \(B\), then \[ |a-b| \le t, \] which is equivalent to \(\max B - \min B \le t\).

Since the answer can be very large, output the result modulo \(10^9+7\).

Note: The sequences are ordered. That is, if a set of numbers forms a valid combination, then all \(m!\) orderings of that set are counted.

inputFormat

Input Format:

1. The first line contains three space‐separated integers \(n\), \(m\), and \(q\).
2. Each of the following \(q\) lines contains two space‐separated integers \(x\) and \(t\), representing a query.

outputFormat

Output Format:

For each query, output a single line containing the number of valid sequences modulo \(10^9+7\).

sample

5 2 2
3 1
4 2

4
8