你正喺度玩一個叫「移除石子」嘅小遊戲。

有 $n$ 堆石仔排成一行，第 $i$ 堆有 $a_i$ 粒。你嘅任務係用以下操作，移走所有石仔：

• 操作一：揀一堆石仔，移走當中至少 2 粒；
• 操作二：揀一個連續編號區間 $[l,r]$（$1\leq l\leq r\leq n$），而且滿足 $r-l\geq 2$，將區間內每堆石仔都恰好移走 1 粒。

你可以按任何順序，執行以上兩種操作任意多次，直到再冇操作可以執行。如果最後移走晒所有石仔，你就贏。

你可能已經開始計算「有幾多種本質上唔同嘅操作方式」之類嘅問題，但實際玩嗰陣，卻發現自己成日輸。所以你打算出個小花招：遊戲開始嗰陣，你手上偷偷藏住 $k$ 粒石仔，喺執行所有操作之前，你可以而且必須將呢啲石仔放入某一堆或某幾堆石仔入面。你希望咁樣可以提高勝算，但亦知道，咁可能令你輸咗原本可以贏嘅遊戲。

而家，你可以自由揀一個初始局面玩遊戲。具體嚟講，每個 $a_i$ 可以揀 $[l_i,r_i]$ 範圍內任何整數。你想計算有幾多種初始局面，令你至少有一種贏嘅方案。因為答案好大，只需要輸出答案對 $10^9+7$ 取模嘅結果。兩個初始局面唔同，當且僅當至少有一個 $1\leq i\leq 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

說明 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\leq 10$，$3\leq n\leq 1000$，$0\leq l_i\leq r_i\leq 10^9$，$0\leq k\leq 100$。