You are playing a game called "Removing Stones."

There are $n$ piles of stones arranged in a row, with the $i$-th pile containing $a_i$ stones. Your task is to remove all stones using the following operations:

• Operation 1: Choose a pile of stones and remove at least 2 stones from it.
• Operation 2: Choose a contiguous range of indices $[l, r]$ ($1 \le l \le r \le n$) such that $r - l \ge 2$, and remove exactly 1 stone from each pile in this range.

You can perform these two operations in any order as many times as you like until no more operations can be performed. You win if you can remove all the stones.

You might have started calculating things like "how many essentially different ways are there to play," but you find that you always lose when actually playing. Therefore, you decide to play a trick: at the beginning of the game, you secretly have $k$ stones in your hand, and before performing any operations, you must place these stones into one or more piles. You hope this will increase your winning rate, but you also realize that this might cause you to lose a game that you could have otherwise won.

Now, you can freely choose an initial configuration to play the game. Specifically, each $a_i$ can be any integer in the range $[l_i, r_i]$. You want to calculate how many initial configurations exist such that you have at least one winning strategy. Since the answer can be very large, you only need to output the result modulo $(10^9 + 7)$. Two initial configurations are different if and only if there exists at least one $1 \le i \le n$ such that their $a_i$ are not equal. Note that "initial configuration" here refers to the configuration before you add the $k$ stones.

Input

The first line contains a positive integer $T$, representing the number of test cases. Then, each test case is given as follows:

The first line contains two integers $n$ and $k$, representing the number of piles and the number of stones to add, respectively.

The next $n$ lines each contain two non-negative integers $l_i, r_i$, representing the range of the initial number of stones in each pile.

Output

For each test case, output a single integer on a new line, representing the number of possible winning configurations modulo $(10^9 + 7)$.

Examples

Input 1

1
4 1
0 1
0 1
0 1
0 1

Output 1

14

Note 1

There are $2^4 = 16$ possible initial configurations. It can be proven that except for the two initial configurations $(0, 0, 0, 0)$ and $(1, 0, 0, 1)$, all other initial configurations have a winning strategy. For example, when the initial configuration is $(1, 0, 1, 0)$, you can place the 1 stone in your hand into the 2nd pile to make the configuration $(1, 1, 1, 0)$, and then perform Operation 2 on the range $[1, 3]$.

Examples 2-4

See the files stone/stone2.in and stone/stone2.ans, stone/stone3.in and stone/stone3.ans, and stone/stone4.in and stone/stone4.ans in the contestant directory.

Constraints

For 100% of the data, $T \le 10$, $3 \le n \le 1000$, $0 \le l_i \le r_i \le 10^9$, $0 \le k \le 100$.