あなたは「石の除去」というミニゲームで遊んでいます。

$n$ 個の石の山が一列に並び、$i$ 番目の山には $a_i$ 個の石があります。次の操作によって、すべての石を取り除くことが目標です。

• 操作 1：山を 1 つ選び、その山から少なくとも 2 個の石を取り除きます。
• 操作 2：$1 \leq l \leq r \leq n$ かつ $r-l \geq 2$ を満たす連続した番号の区間 $[l,r]$ を選び、その区間の各山からちょうど 1 個ずつ石を取り除きます。

上の 2 種類の操作は、操作できなくなるまで、任意の順序で何回でも行えます。最後にすべての石を取り除ければ勝ちです。

あなたはすでに「本質的に異なる操作の方法は何通りあるか」といった問題を計算し始めているかもしれませんが、実際に遊んでみると、いつも負けてしまうことに気付きました。そこで、ちょっとした細工をすることにしました。ゲーム開始時に手の中に $k$ 個の石をこっそり隠し持ち、操作を行う前に、それらの石をいずれか 1 つまたはいくつかの山に追加でき、かつ、必ずすべて追加しなければなりません。これで勝率が上がることを期待していますが、本来は勝てたはずのゲームで負ける可能性もあることは分かっています。

初期状態は自由に選べます。具体的には、各 $a_i$ を $[l_i,r_i]$ 内の任意の整数にできます。少なくとも 1 通りの勝ち方が存在する初期状態が何通りあるかを求めてください。答えは大きくなるため、$(10^9+7)$ で割った余りだけを出力してください。少なくとも 1 つの $1 \leq i \leq n$ が存在し、2 つの状態の $a_i$ が異なるとき、かつそのときに限り、2 つの初期状態は異なるものとします。ここで「初期状態」とは、$k$ 個の石を追加する前の状態を指すことに注意してください。

入力

ファイル stone.in からデータを読み込んでください。

複数のテストケースが与えられます。 1 行目にはテストケース数を表す正整数 $T$ が与えられ、続いて各テストケースが順に与えられます。

各テストケースの 1 行目には、山の個数と追加する石の個数をそれぞれ表す 2 つの整数 $n,k$ が与えられます。続く $n$ 行には、それぞれ 2 つの非負整数 $l_i,r_i$ が与えられ、各山の初期の石の個数の範囲を表します。

出力

ファイル stone.out に出力してください。

各テストケースについて、勝つことのできる初期状態の数を $(10^9+7)$ で割った余りを、1 行に整数で出力してください。

入出力例

入力 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)$ の 2 つの初期状態以外では、どの初期状態からも勝つ方法が存在することを証明できます。例えば、初期状態が $(1\ 0\ 1\ 0)$ の場合、手に持った 1 個の石を 2 番目の山に追加して $(1\ 1\ 1\ 0)$ にし、区間 $[1,3]$ に操作 2 を 1 回行えばよいです。

入出力例 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$ が保証されます。