Problem Description

There is a lottery booth at Huaqing University, and it has $n$ lottery boxes. Initially, each box contains some tickets. Tickets are of two types: winning tickets and empty tickets. In box $i$, there are $a_i$ winning tickets and $b_i$ empty tickets. Each time a student draws, they choose one box and then randomly draw one ticket from the remaining tickets in that box with equal probability, meaning every remaining ticket has the same probability of being drawn. Note that the drawn ticket is not put back into the box.

Now there are $m$ students waiting in line at the booth. They will act in order, and each student performs exactly one operation. Specifically, the student of the $j$-th operation may do one of the following three actions:

1. Draw: for every box from $l_j$ to $r_j$, draw $c_j$ times consecutively from that box. If the number of remaining tickets in a box is less than $c_j$, then draw all remaining tickets in that box.
2. Query: for boxes from $x_j$ to $y_j$, compute the expected value of the sum of the numbers of winning tickets that have been drawn.
3. Add: in box $p_j$, add $u_j$ winning tickets and $v_j$ empty tickets.

Please answer every query. By the nature of the problem, the expected value can always be written as a rational number of the form $\frac{p}{q}$. You need to output its value modulo $10^9+7$ (a prime), i.e. find an $r$ $(0\leq r < 10^9+7)$ such that $qr \equiv p \pmod{10^9+7}$. It can be proven that such an $r$ is unique.

Input Format

The first line contains two positive integers $n,m$, representing the number of lottery boxes and the number of students.

The next $n$ lines each describe a box.

In the $i$-th of these $n$ lines, there are two integers $a_i,b_i$, with the meaning as described above.

The next $m$ lines each describe one student’s operation.

In the $j$-th of these $m$ lines, the first integer $op_j$ indicates the operation type. If $op_j=1$, then three integers $l_j,r_j,c_j$ follow. If $op_j=2$, then two integers $x_j,y_j$ follow. If $op_j=3$, then three integers $p_j,u_j,v_j$ follow. The meanings of the variables are as described above.

All integers on the same line are separated by one space.

The input guarantees:

$0 \leq a_i,b_i,c_j \leq 10^8$.

$0\leq u_j,v_j \leq 10^3$.

$1\leq l_j\leq r_j \leq n$.

$1\leq x_j\leq y_j\leq n$.

$1\leq p_j\leq n$.

$op_j \in \{1,2,3\}$.

Output Format

For each query with $op_j = 2$, output one line containing one integer representing the answer to the query.

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

833333340
83333337

Hint

Sample Explanation 1

After the first student’s operation, the expected number of winning tickets drawn from box 1 is $\frac{1}{3}$.

After the second student’s operation, the expected number of winning tickets drawn from box 2 is $\frac{1}{2}$.

So the third student’s answer is $\frac{1}{3} + \frac{1}{2} = \frac{5}{6}$, and its value modulo $10^9+7$ is $833333340$.

After the fourth student’s operation, box 3 has 3 winning tickets and 1 empty ticket.

After the fifth student’s operation, the expected number of winning tickets drawn from box 3 is $\frac{9}{4}$.

So the sixth student’s answer is $\frac{1}{3} + \frac{1}{2} + \frac{9}{4} = \frac{37}{12}$, and its value modulo $10^9+7$ is $83333337$.

Sample 2

See 2.in/2.ans in the problem attachments.

Sample 3

See 3.in/3.ans in the problem attachments.

Sample 4

See 4.in/4.ans in the problem attachments.

Subtasks

Translated by ChatGPT 5