P10792 "SpOI - R1" The Coolest Kid When Smiling

**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](https://www.luogu.com.cn/problem/P2613).

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.

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$.

### 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$. | Subtask | $T\leq$ | $n\leq$ | Special Property | Score | Subtask Dependencies | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $15$ | $2\times 10^9$ | $A$ | $10$ | None | | 2 | $15$ | $100$ | None | $15$ | None | | 3 | $5$ | $2000$ | None | $15$ | 2 | | 4 | $5$ | $10^6$ | None | $15$ | 2,3 | | 5 | $5$ | $2\times 10^9$ | None | $45$ | 1,2,3,4 | Special Property $A$: it is guaranteed that in the decompressed $a$, every digit appears at most once. Translated by ChatGPT 5