Description

You're playing a little game called Removing Stones.

There are $n$ pile of stones in a line, with $a_i$ stones in the $i$th pile. Your task is to remove all stones by following operations:

• Operation one: Choose one pile of stone, and remove at least $2$ stones from it.

• Operation two: Choose an interval of numbers $[ l,r ] (1 \leq l \leq r \leq n)$ satisfying $r - l \geq 2$, and remove exactly $1$ stone from each of the piles in this range.

You can perform these operations any number of times and in any order, until you can no longer perform any operation. If you're able to remove all stones in the end you win.

You may have already started calculating problems, such as the count of distinct winning operation sequences. However in actual play you always find yourself losing. So you decided to have a trick up sleeve: at the beginning of the game, you'll secretly keep $k$ stones in hour hand. Before all the operations you are able to and must put these stones into one or several piles. You expect this will boost your win rate; although you know this might make you lose games you could have won.

Now you could freely choose a starting position of the game. Specifically, for each $a_i$ you could choose any integer in range $[ l_i,r_i ]$. You want to calculate in how many starting positions you have at least one winning plan. Since the answer is large, you only need to output it modulo $(10^9+7)$. Two starting positions are distinct if and only if there exists at least one $\boldsymbol{1 \leq i \leq n}$ so that $\boldsymbol{a_i}$ of the two are not equal. Note that the starting position refers to the position before you put in $\boldsymbol{k}$ stones.

Input Format

Read from file stone.in.

There are multiple test cases in each test.

The first line of input contains an integer $T$ indicating the number of test cases. Following are the test cases in order.

For each test case, the first line contains two integer $n,k$, each indicating the number of stone piles and the number of stones to be added. The following $n$ lines each consists of two integer $l_i,r_i$ representing the range of initial stone count of each pile.

Output Format

Output to file stone.out.

For each test case, output a line of one integer, indicating the result of winnable position count modulo $(10^9+7)$.

1
4 1
0 1
0 1
0 1
0 1

14

Sample 2

See files [stone2.in](file://stone2.in) and [stone2.ans](file://stone2.ans) in the attachment.

Sample 3

See files [stone3.in](file://stone3.in) and [stone3.ans](file://stone3.ans) in the attachment.

Sample 4

See files [stone4.in](file://stone4.in) and [stone4.ans](file://stone4.ans) in the attachment.

Constraints and Hint

For $100\%$ of the tests, it is guaranteed that $T \leq 10$, $3 \leq n \leq 1000$, $0 \leq l_i \leq r_i \leq 10^9$, $0 \leq k \leq 100$.