[NOI2022] 移除石子

你正在玩一个名为“移除石子”的小游戏。 有 $n$ 堆石子排成一行，第 $i$ 堆有 $a_i$ 枚，你的任务是通过如下的操作将所有石子移除： - 操作一：选择一堆石子，将其中的至少 $2$ 枚石子移除； - 操作二：选择一个连续的编号区间 $[l, r]$（$1 \le l \le r \le n$）并满足 $r - l \ge 2$，将其中的每一堆石子都恰好移除 $1$ 枚。 你可以采用任意顺序执行任意多次上述两种操作，直到无法再执行操作为止。若最后你能将所有石子全部移除则胜利。 你或许已经开始计算起了诸如“有多少种本质不同的操作方式”的问题，但实际玩起来你却发现自己总是在输。因此，你打算玩个小花招：在游戏开始时，你在手里偷偷藏有 $k$ 枚石子，在执行所有操作之前你**可以且必须**将这些石子放入某一堆或某几堆石子中。你期望这会提高自己的胜率，但也清楚这可能会使自己输掉原本可能胜利的游戏。 现在，你可以自由选择一个初始局面进行游戏，具体而言，每个 $a_i$ 可以选择 $[l_i, r_i]$ 范围内的任意整数。你希望计算出，在多少种初始局面下，自己存在至少一种获胜的方案。由于答案很大，你只需要输出其对 $({10}^9 + 7)$ 取模的结果。**两个初始局面不同，当且仅当存在至少一个 $\boldsymbol{1 \le i \le n}$ 使得两者的 $\boldsymbol{a_i}$ 不相等，注意这里的“初始局面”指的是你放入 $\boldsymbol{k}$ 枚石子之前的局面。**

**本题有多组测试数据。** 第一行一个正整数 $T$ 表示测试数据组数，接下来依次给出每组测试数据。 对于每组测试数据，第一行两个整数 $n, k$，分别表示石子堆数和加入的石子个数，接下来 $n$ 行，每行两个非负整数 $l_i, r_i$ 表示每堆石子初始石子数的范围。

对于每组数据输出一行一个整数，表示可能获胜的局面数对$({10}^9 + 7)$ 取模的结果。

1
4 1
0 1
0 1
0 1
0 1

14

**【样例解释 \#1】** 共有 $2^4 = 16$ 种可能的初始局面，可以证明除了 $(0 \ 0 \ 0 \ 0)$ 和 $(1 \ 0 \ 0 \ 1)$ 这两种初始局面无法获胜以外，其余初始局面均存在获胜方案。例如，初始局面为 $(1 \ 0 \ 1 \ 0)$ 时，你可以将手中的 $1$ 枚石子放入第 $2$ 堆石子，使局面变为 $(1 \ 1 \ 1 \ 0)$，再对区间 $[1, 3]$ 使用一次操作二即可。 ---- **【样例 \#2】** 见附件中的 `stone/stone2.in` 与 `stone/stone2.ans`。 ---- **【样例 \#3】** 见附件中的 `stone/stone3.in` 与 `stone/stone3.ans`。 ---- **【样例 \#4】** 见附件中的 `stone/stone4.in` 与 `stone/stone4.ans`。 ---- **【数据范围】** 对于 $100 \%$ 的数据，保证 $T \le 10$，$3 \le n \le 1000$，$0 \le l_i \le r_i \le {10}^9$，$0 \le k \le 100$。 | 测试点编号 | $n \le$ | $k \le$ | 特殊条件 | |:-:|:-:|:-:|:-:| | $1 \sim 3$ | $5$ | $2$ | $r_i \le 5$ | | $4 \sim 5$ | $1000$ | $0$ | $l_i = r_i$ | | $6 \sim 8$ | $1000$ | $100$ | $l_i = r_i$ | | $9 \sim 11$ | $1000$ | $0$ | 无 | | $12 \sim 13$ | $1000$ | $2$ | 无 | | $14 \sim 15$ | $1000$ | $100$ | $r_i \le 10$ | | $16 \sim 20$ | $1000$ | $100$ | 无 |