Problem M. Dylans loves polynomial
时间限制 1000 ms
内存限制 128 MB
First Dylans is given $N$ points $(x_i,y_i)$ in Rectangular Plane Coordinate System.
It guarantees that each $x$ is different.
And there are $Q$ questions.Each question are three numbers:$(L,R,x)$.
His task is to make up a polynomial that its highest coefficient is equal to $(R-L)$.
To check his polynomial,he needs to print the value($y$)of the polynomial by $x$.
Because the value and the pair of points can be very huge,so each calculate must mod $1000000007$.
All points and number $x$ in query are positive integers and not bigger than $250000$.
$2 \leq N \leq 3000,1 \leq Q \leq 3000, 1 \leq L,R \leq N,R>L$
输入数据
输出数据
For each question,output the value of polynomial.
样例输入
复制
4
1 1
2 2
3 3
4 4
3
1 2 1
2 3 3
2 4 1
样例输出
样例说明
You shouldn't print any space in each end of the line in the hack data.
$ Mathjax font initiator $