Problem Description

You are playing a mini-game called “Removing Stones”.

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

• Operation 1: Choose one pile and remove at least $2$ stones from it.
• Operation 2: Choose a consecutive index interval $[l, r]$ ($1 \le l \le r \le n$) satisfying $r - l \ge 2$, and remove exactly $1$ stone from every pile in this interval.

You may perform the two operations in any order, any number of times, until no operation can be performed. If in the end you can remove all stones, you win.

You may already be thinking about questions like “how many essentially different ways of operating are there”, but when you actually play, you find that you keep losing. So you decide to use a trick: before the game starts, you secretly hold $k$ stones in your hand, and before performing any operations you can and must put these stones into one pile or several piles. You hope this will increase your chance of winning, but you also know it might make you lose a game that you could otherwise win.

Now, you may freely choose an initial position to start the game. Specifically, each $a_i$ can be chosen as any integer within the range $[l_i, r_i]$. You want to compute, among all initial positions, for how many of them there exists at least one winning strategy. Since the answer is large, you only need to output it modulo $({10}^9 + 7)$. Two initial positions are different if and only if there exists at least one $\boldsymbol{1 \le i \le n}$ such that their $\boldsymbol{a_i}$ are different. Note that the “initial position” here refers to the position before you put in the $\boldsymbol{k}$ stones.

Input Format

This problem has multiple test cases. The first line contains a positive integer $T$ denoting the number of test cases, followed by the test cases.

For each test case, the first line contains two integers $n, k$, representing the number of piles and the number of stones to add. Then follow $n$ lines, each containing two non-negative integers $l_i, r_i$, representing the range of the initial number of stones in each pile.

Output Format

For each test case, output one integer per line, representing the number of initial positions from which it is possible to win, modulo $({10}^9 + 7)$.

1
4 1
0 1
0 1
0 1
0 1

14

Hint

[Sample Explanation #1]

There are $2^4 = 16$ possible initial positions. It can be proven that except for $(0 \ 0 \ 0 \ 0)$ and $(1 \ 0 \ 0 \ 1)$, these two initial positions cannot be won, all other initial positions have a winning strategy. For example, when the initial position is $(1 \ 0 \ 1 \ 0)$, you can put the $1$ stone in your hand into pile $2$, making the position $(1 \ 1 \ 1 \ 0)$. Then use Operation 2 once on the interval $[1, 3]$.

[Sample #2]

See stone/stone2.in and stone/stone2.ans in the attachment.

[Sample #3]

See stone/stone3.in and stone/stone3.ans in the attachment.

[Sample #4]

See stone/stone4.in and stone/stone4.ans in the attachment.

[Constraints]

For $100\%$ of the testdata, it is guaranteed that $T \le 10$, $3 \le n \le 1000$, $0 \le l_i \le r_i \le {10}^9$, and $0 \le k \le 100$.

Translated by ChatGPT 5