Problem 3771: Junk Junction

Task

In Junk Junction there is an infinite sequence of infinite matrices $A_1,A_2,A_3,\ldots$ , which is defined in the following way:

A_n[i][j]=\begin{cases}0, & \text{if $j \gt i$} \\ 1, & \text{if $j \le i$ and $n=1$} \\ \sum_{k=1}^j A_{n-1}[i][k], & \text{if $j \le i$ and $n \gt 1$} \end{cases}

The $5 \times 5$ upper-left corners of the first $5$ matrices will have the following values:

A_1 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \end{bmatrix}

A_2 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 2 & 0 & 0 & 0 \\ 1 & 2 & 3 & 0 & 0 \\ 1 & 2 & 3 & 4 & 0 \\ 1 & 2 & 3 & 4 & 5 \\ \end{bmatrix}

A_3 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 3 & 0 & 0 & 0 \\ 1 & 3 & 6 & 0 & 0 \\ 1 & 3 & 6 & 10 & 0 \\ 1 & 3 & 6 & 10 & 15 \\ \end{bmatrix}

A_4 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 4 & 0 & 0 & 0 \\ 1 & 4 & 10 & 0 & 0 \\ 1 & 4 & 10 & 20 & 0 \\ 1 & 4 & 10 & 20 & 35 \\ \end{bmatrix}

A_5 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 5 & 0 & 0 & 0 \\ 1 & 5 & 15 & 0 & 0 \\ 1 & 5 & 15 & 35 & 0 \\ 1 & 5 & 15 & 35 & 70 \\ \end{bmatrix}

Given $5$ integers $n$ , $i_1$ , $j_1$ , $i_2$ and $j_2$ , determine the value of:

\sum_{i=i_1}^{i_2}\sum_{j=j_1}^{j_2}A_n[i][j]

Since the answer can be very large, print its remainder modulo $10^9+7$ .

Input data

The first line of input contains a single integer $t$ ( $1 \le t \le 10^5$ ) - the number of test cases.

The first (and only) line of each test case contains $5$ integers $n$ , $i_1$ , $j_1$ , $i_2$ and $j_2$ ( $1 \le n ,i_1,j_1,i_2,j_2 \le 10^6$ , $i_1 \le i_2$ , $j_1 \le j_2$ ).

Output data

For each test case, print the sum of the elements from the corresponding submatrix.

Since the answer can be very large, print its remainder modulo $10^9+7$ .

Example

stdin

6
2 2 1 4 4
1 3 2 4 5
3 1 1 5 5
5 3 2 5 4
1000000 1 2 1 1000000
15 11 9 25 20

stdout

Explanation

In the first test case, the submatrix from $A_2$ whose corners are in $(2,1)$ , and $(4,4)$ , respectively, contains the following values:

\begin{bmatrix} 1 & 2 & 0 & 0 \\ 1 & 2 & 3 & 0 \\ 1 & 2 & 3 & 4 \\ \end{bmatrix}

The sum of these values is equal to: $1+1+1+2+2+2+3+3+4=19$ .

In the second test case, the submatrix from $A_1$ whose corners are in $(3,2)$ , and $(4,5)$ , respectively, contains the following values:

\begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ \end{bmatrix}

The sum of these values is equal to: $1+1+1+1+1=5$ .

Junk Junction

Task

Input data

Output data

Example

Explanation

Log in or sign up to be able to send submissions!