Du spielst ein kleines Spiel namens „移除石子“.

Es gibt $n$ Steinhaufen in einer Reihe; der $i$-te enthält $a_i$ Steine. Deine Aufgabe ist es, mithilfe der folgenden Operationen alle Steine zu entfernen:

• Operation 1: Wähle einen Steinhaufen und entferne mindestens $2$ seiner Steine.
• Operation 2: Wähle ein zusammenhängendes Intervall von Haufennummern $[l,r]$ mit $1\le l\le r\le n$ und $r-l\ge 2$. Entferne aus jedem Haufen in diesem Intervall genau $1$ Stein.

Du darfst die beiden Operationen beliebig oft und in beliebiger Reihenfolge ausführen, bis keine Operation mehr möglich ist. Wenn du am Ende sämtliche Steine entfernt hast, gewinnst du.

Vielleicht hast du bereits angefangen, Fragen wie „Wie viele wesentlich verschiedene Operationsfolgen gibt es?“ zu berechnen. Beim tatsächlichen Spielen stellst du jedoch fest, dass du ständig verlierst. Deshalb planst du einen kleinen Trick: Zu Beginn des Spiels versteckst du heimlich $k$ Steine in deiner Hand. Bevor du irgendeine Operation ausführst, darfst und musst du diese Steine auf einen oder mehrere Haufen legen. Du hoffst, damit deine Gewinnchancen zu erhöhen, weißt aber auch, dass du dadurch ein Spiel verlieren könntest, das du ursprünglich hättest gewinnen können.

Nun kannst du die Anfangsstellung frei wählen: Jedes $a_i$ darf eine beliebige ganze Zahl aus dem Bereich $[l_i,r_i]$ sein. Berechne, für wie viele Anfangsstellungen mindestens eine Gewinnmöglichkeit existiert. Da die Antwort sehr groß ist, gib sie nur modulo $10^9+7$ aus. Zwei Anfangsstellungen sind genau dann verschieden, wenn es mindestens ein $i$ mit $1\le i\le n$ gibt, dessen Wert $a_i$ sich in beiden Stellungen unterscheidet. Beachte, dass „Anfangsstellung“ hier die Stellung vor dem Hinzufügen der $k$ Steine bezeichnet.

Eingabe

Lies die Daten aus der Datei stone.in.

Diese Aufgabe enthält mehrere Testdatensätze. Die erste Zeile enthält eine positive ganze Zahl $T$, die Anzahl der Testdatensätze. Danach werden diese der Reihe nach angegeben.

Für jeden Testdatensatz enthält die erste Zeile zwei ganze Zahlen $n,k$, die Anzahl der Steinhaufen und die Anzahl der hinzuzufügenden Steine. Es folgen $n$ Zeilen mit jeweils zwei nichtnegativen ganzen Zahlen $l_i,r_i$, die den Bereich der anfänglichen Steinanzahl des jeweiligen Haufens angeben.

Ausgabe

Schreibe die Ausgabe in die Datei stone.out.

Gib für jeden Datensatz eine Zeile mit einer ganzen Zahl aus: die Anzahl der Stellungen mit einer Gewinnmöglichkeit modulo $10^9+7$.

Beispiele

Eingabe 1

1
4 1
0 1
0 1
0 1
0 1

Ausgabe 1

14

Hinweis

Es gibt insgesamt $2^4=16$ mögliche Anfangsstellungen. Man kann beweisen, dass für alle außer $(0,0,0,0)$ und $(1,0,0,1)$ eine Gewinnmöglichkeit existiert. Beispielsweise kannst du bei der Anfangsstellung $(1,0,1,0)$ den einen Stein in deiner Hand auf den 2. Haufen legen. Damit entsteht $(1,1,1,0)$, und eine Anwendung von Operation 2 auf das Intervall $[1,3]$ genügt.

Beispiel 2

Siehe stone/stone2.in und stone/stone2.ans im Teilnehmerverzeichnis.

Beispiel 3

Siehe stone/stone3.in und stone/stone3.ans im Teilnehmerverzeichnis.

Beispiel 4

Siehe stone/stone4.in und stone/stone4.ans im Teilnehmerverzeichnis.

Beschränkungen

Für $100\%$ der Daten gilt: $T\le 10$, $3\le n\le 1000$, $0\le l_i\le r_i\le 10^9$, $0\le k\le 100$.