题目描述

本题包含多组数据。

有一个数字序列 $a$，长度为 $n$。序列中每一项均为 $0$ 到 $9$ 的数字。

另有一个空数字序列 $b$，$b$ 中会出现一个光标（你可以理解为能够出现在数字之间，或整个数字序列之前，或整个数字序列之后的细线），此时光标前后均没有数字。

现在向 $b$ 中依次输入数字序列 $a$。每输入一个数字，数字立即出现在光标之后。

接下来光标立即随机地移动到任意一个数字之前或所有数字之后。随机是均匀的。换句话说，光标移动到所有可移动到的位置的概率是均等的。

现在告诉你数字序列 $a$。你需要输出的是，最终得到的 $b$ 直接转为十进制后的大小（无视前导零）的期望，对质数 $2007072007$ 取模。

由于 $a$ 可能很长，所以本题采用压缩输入。

具体来说，最开始 $a$ 是空的数字序列，输入会给你一个 $k$ 长的二元组数组，其中第 $i$ 项为 $(x_i,l_i)$，表示数字 $x_i$ 连续出现 $l_i$ 次接在之前的 $a$ 之后。你可以用此方法解压缩真正的 $a$，再解决问题。

在本题，你可以对期望的理解：对于一个变量可能的结果 $X$，若其权值为 $v_X$，得到该结果的概率为 $p_X$，则对于结果集 $S$，变量的期望 $E=\sum\limits_{X\in S}p_Xv_X$。

如果你不知道如何对有理数取模：请查看此题。

输入格式

第一行一个整数 $T$，表示数据组数。

对于每组数据：

一行一个整数 $k$，表示 $a$ 压缩后得到的二元组数组包含多少项。

接下来共 $k$ 行，每行两个整数 $x_i,l_i$，表示在上一项所得 $a$ 序列的基础上，在末尾增加 $l_i$ 个数字 $x_i$ 得到新的 $a$ 序列。你可以用这种方式解压缩真正的 $a$ 序列。

输出格式

对于每组数据，输出一行一个整数，表示在光标每次都随机移动的情况下，可能得到的 $b$ 转化为十进制后的大小（无视前导零）的期望，对质数 $2007072007$ 取模的值。

1
2
4 1
2 1

33

1
3
1 2
3 1
7 2

1204285426

提示

数据范围

本题开启子任务捆绑和子任务依赖。

令 $n=\sum\limits_{i=1}^k l_i$。

对于 $100\%$ 的数据，保证 $1\leq T\leq 15$，$1\leq n\leq 2\times 10^9$，$1\leq k\leq 10^5$，且对于任意 $i$ 均有 $0\leq a_i\leq 9$，$1\leq l_i\leq 2\times 10^9$。

特殊性质 $A$：保证在解压缩后的 $a$ 中，任意一个数字都出现了最多一次。