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 \)