L. MEXpected Value
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given arrays $$$a$$$, $$$p$$$, and $$$q$$$ of $$$n$$$ nonnegative integers each, and a multiset $$$S$$$ that is initially empty. For each $$$1 \le i \le n$$$ in order, you then add $$$a_i$$$ to $$$S$$$ with probability $$$\frac{p_i}{q_i}$$$. What is the expected value of the $$$\operatorname{MEX}$$$ of $$$S$$$ at the end of this process, taken modulo $$$10^9+7$$$?

The $$$\operatorname{MEX}$$$ of a set of integers is defined as the smallest non-negative integer which does not occur in the set. For example, the $$$\operatorname{MEX}$$$ of $$$\{0, 1, 2, 4\}$$$ is $$$3$$$, and the $$$\operatorname{MEX}$$$ of $$$\{1, 4, 6, 8\}$$$ is $$$0$$$.

Input

Each test consists of multiple test cases.

The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the length of the array $$$a$$$.

The $$$i$$$-th of the next $$$n$$$ lines contains three integers $$$a_i$$$, $$$p_i$$$, and $$$q_i$$$ ($$$0 \le a_i \le n$$$, $$$0 \le p_i \le 10^9$$$, $$$\max(1, p_i) \le q_i \le 10^9$$$, $$$p_i$$$ and $$$q_i$$$ are coprime) — $$$a_i$$$ and the two values representing the probability that $$$a_i$$$ is added to $$$S$$$, as described above, respectively.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output the expected $$$\operatorname{MEX}$$$ of $$$S$$$ modulo $$$10^9+7$$$.

Formally, it can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{x}{y}$$$, where $$$x$$$ and $$$y$$$ are integers and $$$y\not\equiv 0 \mod 10^9+7$$$. Output the integer equal to $$$x\cdot y^{-1}\mod 10^9+7$$$. In other words, output the integer $$$k$$$ such that $$$0\leq k \lt 10^9+7$$$ and $$$k\cdot y\equiv x \mod 10^9+7$$$.

Example
Input
5
1
0 1 3
2
0 1 2
1 1 2
3
0 1 2
0 1 2
0 1 2
6
0 1 4
6 2 7
1 4 9
1 2 5
2 1 1
0 3 5
5
0 1 1
1 4 7
2 3 8
3 19 20
4 0 1
Output
333333336
750000006
875000007
433333338
389285719
Note

In the first test case, we include $$$a_1 = 0$$$ in $$$S$$$ with probability $$$\frac{1}{3}$$$. So $$$\frac{1}{3}$$$ of the time, $$$S = \{0\}$$$, which has a $$$\operatorname{MEX}$$$ of $$$1$$$, and otherwise $$$S = \{\}$$$, with a $$$\operatorname{MEX}$$$ of $$$0$$$.

Therefore the expected value of the $$$\operatorname{MEX}$$$ is $$$\frac{1}{3}$$$, which is $$$333333336$$$ modulo $$$10^9+7$$$.

In the second test case, we include $$$a_1 = 0$$$ in $$$S$$$ with probability $$$\frac{1}{2}$$$ and $$$a_2 = 1$$$ in $$$S$$$ with probability $$$\frac{1}{2}$$$. So there are four possible outcomes for $$$S$$$, each with probability $$$\frac{1}{4}$$$ of occurring:

  • $$$S = \{\}$$$ with a $$$\operatorname{MEX}$$$ of $$$0$$$
  • $$$S = \{0\}$$$ with a $$$\operatorname{MEX}$$$ of $$$1$$$
  • $$$S = \{1\}$$$ with a $$$\operatorname{MEX}$$$ of $$$0$$$
  • $$$S = \{0, 1\}$$$ with a $$$\operatorname{MEX}$$$ of $$$2$$$

So the expected value of the $$$\operatorname{MEX}$$$ is $$$\frac{0 + 1 + 0 + 2}{4} = \frac{3}{4}$$$, which is $$$750000006$$$ modulo $$$10^9+7$$$.

In the third test case, we include $$$a_1 = 0$$$, $$$a_2 = 0$$$, and $$$a_3 = 0$$$ in $$$S$$$ each with independent probability $$$\frac{1}{2}$$$. So there is a $$$\frac{7}{8}$$$ chance that we include at least one of them and the $$$\operatorname{MEX}$$$ of $$$S$$$ is $$$1$$$, and otherwise $$$S$$$ is empty with a $$$\operatorname{MEX}$$$ of $$$0$$$. So the expected value of the $$$\operatorname{MEX}$$$ is $$$\frac{7}{8}$$$, which is $$$875000007$$$ modulo $$$10^9+7$$$.