You are playing a game called "Remove Stones". There are ~n~ piles of stones lined up in a row, the ~i~-th pile has ~a_i~ stones in it, your task is to remove all the stones through the following operations:

• Select a pile of stones and remove at least ~2~ stones;
• Select a contiguous interval ~[l, r]~ (~1 \leq l \leq r \leq n~) which satisfies ~r - l \geq 2~ , remove exactly 1 stone from each pile in the interval.

You can perform the above two operations any number of times in any order until you can no longer perform the operations. If you can remove all the stones, you win.

You have ~k~ stones secretly hidden in the beginning, you must put these stones into a certain pile or in some piles of stones before the game starts. You can choose any configuration of putting in the ~k~ extra stones. For each pile, there is a range that the number of stones in it must lie in, specifically, each ~a_i~ can be chosen from any integer in the range ~[l_i, r_i]~. Find the number of winning configurations modulo ~(10^9 + 7)~.

Two configurations are different if and only if there exists at least one ~i~ (~1 \leq i \leq n~) such that ~a_i~ differs in the two initial configurations. Here, "initial configurations" refer to the configuration before putting the ~k~ stones into the piles.

Input Specifications

The first line is an integer ~T~, the number of subcases in the data.

For each test case, there are two integers ~n~ and ~k~ in the first line, representing the number of piles of stones and the number of stones added, respectively, and the next ~n~ lines, each with two non-negative integers ~l_i~ and ~r_i~, represent the range of the initial number of stones in each pile of stones.

Output Specifications

For each test case, output a line with an integer denoting the number of winning initial positions modulo ~10^9+7~.

Sample inputs and outputs can be found here.

Sample Input 1

1
4 1
0 1
0 1
0 1
0 1

Sample Output 1

14

Explanation for Sample 1

There are ~2^4 = 16~ possible initial positions, there are only 2 losing configurations, ~(0\ 0\ 0\ 0), (1\ 0\ 0\ 1)~

Examples 2-4

See stone/stone(2-4).in and stone/stone(2-4).out

Constraints

• For all test cases, ~T \leq 10~, ~3 \leq n \leq 1000~, ~0 \leq l_i \leq r_i \leq 10^9~, ~0 \leq k \leq 100~.
• Test case 1-3: ~n \leq 5~, ~k \leq 2~, ~r_i \leq 5~.
• Test case 4-5: ~k = 0~, ~l_i = r_i~.
• Test case 6-8: ~l_i = r_i~.
• Test case 9-11: ~k = 0~.
• Test case 12-13: ~k \leq 2~.
• Test case 14-15: ~r_i \leq 100~.
• Test case 16-20: no additional constraints.