Preparing NOJ

Kejin Player

5000ms 0K


Cuber QQ always envies those Kejin players, who pay a lot of RMB to get a higher level in the game. So he worked so hard that you are now the game designer of this game. He decided to annoy these Kejin players a little bit, and give them the lesson that RMB does not always work.

This game follows a traditional Kejin rule of "when you are level $$$i$$$, you have to pay $$$a_i$$$ RMB to get to level $$$i+1$$$". Cuber QQ now changed it a little bit: "when you are level $$$i$$$, you pay $$$a_i$$$ RMB, are you get to level $$$i+1$$$ with probability $$$p_i$$$; otherwise you will turn into level $$$x_i$$$ ($$$x_i \le i$$$)".

Cuber QQ still needs to know how much money expected the Kejin players needs to ``ke'' so that they can upgrade from level $$$l$$$ to level $$$r$$$, because you worry if this is too high, these players might just quit and never return again.


The first line of the input is an integer $$$t$$$, denoting the number of test cases.

For each test case, there is two space-separated integers $$$n$$$ ($$$1 \le n \le 500~000$$$) and $$$q$$$ ($$$1 \le q \le 500~000$$$) in the first line, meaning the total number of levels and the number of queries.

Then follows $$$n$$$ lines, each containing integers $$$r_i$$$, $$$s_i$$$, $$$x_i$$$, $$$a_i$$$ ($$$1 \le r_i \le s_i \le 10^9$$$, $$$1 \le x_i \le i$$$, $$$0 \le a_i \le 10^9$$$), space separated. Note that $$$p_i$$$ is given in the form of a fraction $$$\frac{r_i}{s_i}$$$.

The next $$$q$$$ lines are $$$q$$$ queries. Each of these queries are two space-separated integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n + 1$$$).

The sum of $$$n$$$ and sum of $$$q$$$ from all $$$t$$$ test cases both does not exceed $$$10^6$$$.


For each query, output answer in the fraction form modulo $$$10^9+7$$$, that is, if the answer is $$$\frac{P}{Q}$$$, you should output $$$P \cdot Q^{-1}$$$ modulo $$$10^9+7$$$, where $$$Q^{-1}$$$ denotes the multiplicative inverse of $$$Q$$$ modulo $$$10^9+7$$$.

Sample Input:

3 2
1 1 1 2
1 2 1 3
1 3 3 4
1 4
3 4

Sample Output:


Huge IO (Over 40MB)! IO optimization is preferred.



Provider HDU

Origin HDU854-1011

Code HDU6656


Submitted 146

Passed 13

AC Rate 8.9%

Date 08/12/2019 12:07:44


Nothing Yet