F. How Many Valid Collections?
time limit per test
4 seconds
memory limit per test
32 megabytes
input
standard input
output
standard output

For any positive integer $$$n$$$, let $$$S$$$ be its decimal representation without leading zeros. A subsequence of $$$n$$$ of length $$$k$$$ is formed by selecting $$$k$$$ indices $$$1 \le i_1 \lt i_2 \lt \dots \lt i_k \le |S|$$$.

Two subsequences are considered different if their sets of chosen indices are different, even if the resulting strings of digits are identical.

Let $$$F(n, k, d)$$$ be the number of different subsequences of $$$n$$$ of length $$$k$$$ that consist of exactly $$$d$$$ distinct digit values.

You are given a range $$$[L, R]$$$ and $$$Q$$$ independent queries. For each query $$$(k, d)$$$, calculate: $$$$$$ \sum_{i=L}^{R} F(i, k, d) $$$$$$

Since the result can be large, output it modulo $$$(10^9 + 7)$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$L$$$ $$$(1 \le L \le 10^{100})$$$.

The second line of each test case contains an integer $$$R$$$ $$$(L \le R \le 10^{100})$$$.

The third line of each test case contains a single integer $$$Q$$$ $$$(1 \le Q \le 10^6)$$$ — the number of queries.

Each of the next $$$Q$$$ lines contains two integers $$$k$$$ and $$$d$$$ $$$(1 \le k \le |R|, 1 \le d \le 10)$$$.

It is guaranteed that the sum of $$$Q$$$ over all test cases does not exceed $$$10^6$$$.

It is guaranteed that the sum of $$$|R|^2$$$ over all test cases does not exceed $$$12000$$$, where $$$|R|$$$ denotes the number of digits in $$$R$$$.

Output

For each test case, output $$$Q$$$ lines. For each query, print a single integer — the total number of valid subsequences modulo $$$(10^9 + 7)$$$.

Example
Input
2
1
1
1
1 1
1
12
2
1 1
1 2
Output
1
15
0
Note

In the first test case, $$$L=1$$$ and $$$R=1$$$. For the query $$$(k=1, d=1)$$$, the only integer is $$$1$$$. Its only subsequence of length $$$1$$$ is "1", which has exactly $$$1$$$ distinct digit. Thus, the answer is $$$1$$$.

In the second test case, $$$L=1$$$ and $$$R=12$$$.

For $$$(k=1, d=1)$$$, any single digit is a valid subsequence. Thus, $$$F(n, 1, 1)$$$ is simply the number of digits in $$$n$$$:

  • Numbers $$$1$$$ to $$$9$$$ each have $$$1$$$ digit, contributing $$$9 \times 1 = 9$$$.
  • Numbers $$$10, 11, 12$$$ each have $$$2$$$ digits, contributing $$$3 \times 2 = 6$$$.
The total sum is $$$9 + 6 = 15$$$.

For the second query $$$(k=1, d=2)$$$: A subsequence of length $$$k=1$$$ contains only one digit. It is mathematically impossible for a single digit to result in $$$d=2$$$ distinct values. Therefore, $$$F(n, 1, 2) = 0$$$ for all $$$n$$$, and the sum is $$$0$$$.