There is a matrix and two DOTA warriors Luna and crystal stand at a starting point $(u,v)$ and want to reach some final point $(x,y)$ but as they are arch rivals they don't want to meet before the final points. Find Number of such path from $(u,v)$ to $(x,y)$.

Luna and crystal are allowed to move from (a,b) to (a+1,b) or (a,b+1)

There are m such kind of queries and you have to print answer MOD 1000000007.

Input

First line of input contain a single integer n number of rows and columns of matrix. Second line of input contains an integer m m. m lines follows each line contain four integer $u,v,x,y$

Output

Print m lines answer of ith query in the ith line.

Constraints

$n,m \le 100000$

$1\le u,v,x,y \le n$

$u \le x$

$v \le y$