Grasz w niewielką grę o nazwie „Usuwanie kamieni”.

W rzędzie znajduje się $n$ stosów kamieni; na $i$-tym stosie jest $a_i$ kamieni. Twoim zadaniem jest usunąć wszystkie kamienie za pomocą następujących operacji:

• Operacja pierwsza: wybierz jeden stos i usuń z niego co najmniej $2$ kamienie.
• Operacja druga: wybierz przedział kolejnych indeksów $[l,r]$ ($1\le l\le r\le n$) spełniający $r-l\ge2$ i usuń dokładnie $1$ kamień z każdego stosu w tym przedziale.

Możesz wykonywać obie operacje w dowolnej kolejności dowolną liczbę razy, aż żadnej z nich nie da się już wykonać. Wygrywasz, jeśli ostatecznie usuniesz wszystkie kamienie.

Być może zacząłeś już obliczać takie rzeczy jak „liczba zasadniczo różnych sposobów wykonywania operacji”, ale podczas gry zauważasz, że ciągle przegrywasz. Postanawiasz więc zastosować małą sztuczkę: na początku gry potajemnie trzymasz w dłoni $k$ kamieni. Przed wykonaniem jakiejkolwiek operacji możesz i musisz dołożyć wszystkie te kamienie do jednego lub kilku stosów. Liczysz na zwiększenie szans na wygraną, ale zdajesz sobie sprawę, że może to również zepsuć pozycję, z której wcześniej dało się wygrać.

Teraz możesz dowolnie wybrać pozycję początkową: każde $a_i$ może być dowolną liczbą całkowitą z przedziału $[l_i,r_i]$. Oblicz, dla ilu pozycji początkowych istnieje co najmniej jeden sposób wygrania. Ponieważ wynik jest duży, wypisz go modulo $(10^9+7)$. Dwie pozycje początkowe są różne wtedy i tylko wtedy, gdy dla co najmniej jednego $1\le i\le n$ mają różne wartości $a_i$. Zwróć uwagę, że „pozycja początkowa” oznacza pozycję przed dołożeniem $k$ kamieni.

Wejście

Dane należy wczytać z pliku stone.in.

Wejście zawiera wiele zestawów danych. Pierwszy wiersz zawiera dodatnią liczbę całkowitą $T$, oznaczającą ich liczbę. Dalej podane są kolejno wszystkie zestawy.

Dla każdego zestawu pierwszy wiersz zawiera dwie liczby całkowite $n,k$, oznaczające odpowiednio liczbę stosów oraz liczbę dokładanych kamieni. Następne $n$ wierszy zawiera po dwie nieujemne liczby całkowite $l_i,r_i$, określające zakres początkowej liczby kamieni na danym stosie.

Wyjście

Wynik należy zapisać do pliku stone.out.

Dla każdego zestawu wypisz w osobnym wierszu jedną liczbę całkowitą: liczbę pozycji, z których można wygrać, modulo $(10^9+7)$.

Przykład

Wejście 1

1
4 1
0 1
0 1
0 1
0 1

Wyjście 1

14

Uwagi

Istnieje $2^4=16$ możliwych pozycji początkowych. Można wykazać, że z każdej poza $(0\ 0\ 0\ 0)$ i $(1\ 0\ 0\ 1)$ da się wygrać. Na przykład dla pozycji $(1\ 0\ 1\ 0)$ możesz dołożyć trzymany w dłoni $1$ kamień do drugiego stosu, uzyskując $(1\ 1\ 1\ 0)$, a następnie wykonać operację drugą na przedziale $[1,3]$.

Przykład 2

Zobacz pliki stone/stone2.in i stone/stone2.ans w katalogu zawodnika.

Przykład 3

Zobacz pliki stone/stone3.in i stone/stone3.ans w katalogu zawodnika.

Przykład 4

Zobacz pliki stone/stone4.in i stone/stone4.ans w katalogu zawodnika.

Ograniczenia

Dla $100\%$ danych zachodzi $T\le10$, $3\le n\le1000$, $0\le l_i\le r_i\le10^9$, $0\le k\le100$.