你正在玩一個名為「移除石子」的小遊戲。

有 $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)$ 取模的結果。兩個初始局面不同，若且唯若存在至少一個 $1\le i\le n$ 使得兩者的 $a_i$ 不相等，注意這裡的「初始局面」指的是你放入 $k$ 枚石子之前的局面。

輸入格式

從檔案 stone.in 中讀入資料。

本題有多組測試資料。第一行一個正整數 $T$ 表示測試資料組數，接下來依次給出每組測試資料。

對於每組測試資料，第一行兩個整數 $n,k$，分別表示石子堆數和加入的石子個數，接下來 $n$ 行，每行兩個非負整數 $l_i,r_i$ 表示每堆石子初始石子數的範圍。

輸出格式

輸出到檔案 stone.out 中。

對於每組資料輸出一行一個整數，表示可能獲勝的局面數對 $(10^9+7)$ 取模的結果。

範例

輸入格式 1

1
4 1
0 1
0 1
0 1
0 1

輸出格式 1

14

說明

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