题目描述

你正在玩一个名为“移除石子”的小游戏。

有 $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

样例输入 #1

1
4 1
0 1
0 1
0 1
0 1

样例输出 #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$。