Expected Value After Random Cursor Insertion

Given a digit sequence a of length \(n\) (each digit is between 0 and 9) and an initially empty sequence b with a cursor, we perform the following process:

• Initially, b is empty and the cursor is placed at the beginning (i.e. before any digit).
• Then, for each digit in a (processed in order), the digit is inserted immediately after the cursor.
• After each insertion, the cursor jumps uniformly at random to one of the available gaps in b. (A gap is defined as a location before the first digit, between two consecutive digits, or after the last digit.)

Note that the process of inserting each digit in this way produces a uniformly random permutation of the digits in a (even if some digits are identical). When the final sequence b is interpreted as a decimal number (ignoring any leading zeros), its value is determined by the positions of the digits.

It can be shown that the expected value of the resulting number is given by

\[ E = \frac{\sum_{i=1}^{n}a_i}{n} \cdot \frac{10^n - 1}{9} \quad (\bmod\ 2007072007), \]

where the computation is performed modulo the prime number \(2007072007\). All divisions must be handled via modular inverses.

The input is given in a compressed format: the sequence a starts empty and is built by appending groups of identical digits.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each test case begins with an integer \(k\) — the number of groups. Then \(k\) lines follow, each containing two integers \(x_i\) and \(l_i\), which denote that the digit \(x_i\) appears consecutively \(l_i\) times appended to the current sequence a.

outputFormat

For each test case, output a single integer: the expected value of the decimal number formed by the final sequence b (ignoring leading zeros) modulo \(2007072007\).

sample

3
1
1 1
2
1 1
2 1
1
0 3

1
[Value2]
0

</p>