There is a grid of dimension $n \times m$. Khatru is at the point $(1,1)$ and he needs to go to the point $(n, m)$ in the grid. The only constraint is that he needs to pass through the point $(x, y)$. He can only move towards right or down.

Help him by finding the number of ways, he can do so. As the answer can be large, output it % $1000000007$.

Input

The first line contains an integer q denoting the total number of queries.

Each of the next q lines contains 4 integers x, y, n, m.

Output

For each test case, print an integer denoting the total number of ways to reach the point $(n, m)$.

Constraints

$1 \le q \le 10^5$

$1 \le x \le n$

$1 \le y \le m$

Subtask 1: 20 Points

$1\le n \le 10^3$

$1\le m \le 10^3$

Subtask 2: 80 Points

$1\le n \le 10^6$

$1\le m \le 10^6$