Problem Description

This problem contains multiple sets of data.

There is a sequence of digits $a$ with a length of $n$. Each element in the sequence is a digit from $0$ to $9$.

Another sequence $b$ is initially empty, and it contains a cursor (which you can think of as a thin line that can appear between digits, before the entire sequence, or after the entire sequence), with no digits before or after the cursor.

Now, the sequence $a$ is input into $b$ sequentially. Each time a digit is input, it immediately appears after the cursor.

Next, the cursor immediately moves randomly to any position before a digit or after all digits. The randomness is uniform. In other words, the probability of the cursor moving to any possible position is equal.

You are given the sequence $a$. You need to output the expected value of the decimal representation of the final sequence $b$ (ignoring leading zeros), modulo the prime number $2007072007$.

Since $a$ might be very long, the input is compressed.

Specifically, $a$ starts as an empty sequence. The input will give you an array of $k$ pairs, where the $i$-th pair is $(x_i, l_i)$, indicating that the digit $x_i$ appears $l_i$ times consecutively at the end of the previous $a$ sequence. You can decompress the actual $a$ using this method and then solve the problem.

Understanding of expectation in this problem: For a variable with possible outcomes $X$, if its weight is $v_X$ and the probability of obtaining this outcome is $p_X$, then for the set of outcomes $S$, the expected value $E = \sum_{X \in S} p_X v_X$.

If you do not know how to take the modulo of a rational number: Please refer to this problem.

Input Format

The first line contains an integer $T$, representing the number of data sets.

For each data set:

The first line contains an integer $k$, representing the number of pairs in the compressed array of $a$.

The next $k$ lines each contain two integers $x_i, l_i$, indicating that $l_i$ instances of the digit $x_i$ are added consecutively at the end of the previous $a$ sequence. You can decompress the actual $a$ sequence using this method.

Output Format

For each data set, output a single integer representing the expected value of the decimal representation of the final sequence $b$ (ignoring leading zeros) under the condition that the cursor moves randomly each time, modulo the prime number $2007072007$.

Sample Input and Output

Sample Input #1

1
2
4 1
2 1

Sample Output #1

33

Sample Input #2

1
3
1 2
3 1
7 2

Sample Output #2

1204285426

Notes

Data Range

This problem has subtask bundling and dependency.

Let $n = \sum_{i=1}^k l_i$.

For $100\%$ of the data, it is guaranteed that $1 \leq T \leq 15$, $1 \leq n \leq 2 \times 10^9$, $1 \leq k \leq 10^5$, and for any $i$, $0 \leq a_i \leq 9$, $1 \leq l_i \leq 2 \times 10^9$.

Special Condition $A$: It is guaranteed that after decompression, each digit in $a$ appears at most once.

见题面 Input 部分

见题面 Output 部分