

Kejin PlayerTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 2405 Accepted Submission(s): 1005 Problem Description 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. Input The first line of the input is an integer $t$, denoting the number of test cases. For each test case, there is two spaceseparated 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 spaceseparated 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$. Output 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
Sample Output
Hint Huge IO (Over 40MB)! IO optimization is preferred. Source  
