Problem Description

This problem contains multiple test cases.

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

There is also an empty digit sequence $b$. A cursor will appear in $b$ (you can think of it as a thin line that can appear between digits, before the whole digit sequence, or after the whole digit sequence). At this time, there are no digits on either side of the cursor.

Now input the digit sequence $a$ into $b$ in order. Each time you input one digit, the digit immediately appears after the cursor.

Then the cursor immediately moves randomly to a position before any digit or to after all digits. The randomness is uniform. In other words, the probability that the cursor moves to any movable position is equal.

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

Since $a$ may be very long, this problem uses compressed input.

Specifically, initially $a$ is an empty digit sequence. The input will give you an array of $k$ pairs, where the $i$-th item is $(x_i,l_i)$, meaning the digit $x_i$ appears consecutively $l_i$ times appended to the end of the previous $a$. You can use this method to decompress the real $a$, and then solve the problem.

How to understand expectation in this problem: For a variable with possible outcomes $X$, if the value of outcome $X$ is $v_X$ and the probability of obtaining it is $p_X$, then for the outcome set $S$, the expectation is $E=\sum\limits_{X\in S}p_Xv_X$.

If you do not know how to take a rational number modulo: please see this problem.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case:

One line contains an integer $k$, the number of items in the pair array after compressing $a$.

Then there are $k$ lines, each containing two integers $x_i,l_i$, meaning that based on the $a$ sequence obtained from the previous item, you append $l_i$ digits $x_i$ at the end to get the new $a$ sequence. You can decompress the real $a$ sequence in this way.

Output Format

For each test case, output one integer per line, representing the expected value of the possible $b$ (interpreted as a decimal number, ignoring leading zeros) when the cursor moves randomly each time, modulo the prime $2007072007$.

1
2
4 1
2 1

33

1
3
1 2
3 1
7 2

1204285426

Hint

Constraints

This problem uses subtask bundling and subtask dependencies.

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

For $100\%$ of the testdata, 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 Property $A$: it is guaranteed that in the decompressed $a$, every digit appears at most once.

Translated by ChatGPT 5