Vous jouez à un petit jeu appelé « Retirer les pierres ».

Il y a $n$ tas de pierres alignés, le $i$-ième contenant $a_i$ pierres. Votre tâche est de retirer toutes les pierres à l'aide des opérations suivantes :

• Opération 1 : choisir un tas et en retirer au moins $2$ pierres.
• Opération 2 : choisir un intervalle de numéros consécutifs $[l,r]$ ($1\le l\le r\le n$) tel que $r-l\ge2$, et retirer exactement $1$ pierre de chacun des tas de cet intervalle.

Vous pouvez effectuer ces deux opérations autant de fois que vous le souhaitez, dans n'importe quel ordre, jusqu'à ce qu'aucune opération ne soit plus possible. Vous gagnez si vous réussissez à retirer toutes les pierres.

Vous avez peut-être déjà commencé à étudier des questions telles que « combien y a-t-il de suites d'opérations essentiellement différentes ? », mais en jouant réellement, vous constatez que vous perdez sans cesse. Vous décidez donc de tricher un peu : au début du jeu, vous cachez $k$ pierres dans votre main. Avant d'effectuer la moindre opération, vous pouvez et devez ajouter toutes ces pierres à un ou plusieurs tas. Vous espérez améliorer ainsi vos chances de gagner, tout en sachant que cela peut aussi vous faire perdre une partie que vous auriez pu gagner.

Vous pouvez maintenant choisir librement une configuration initiale : chaque $a_i$ peut être n'importe quel entier de $[l_i,r_i]$. Calculez le nombre de configurations initiales pour lesquelles il existe au moins une stratégie gagnante. Comme la réponse est très grande, affichez-la modulo $10^9+7$. Deux configurations initiales sont différentes si et seulement s'il existe au moins un $1\le i\le n$ pour lequel leurs valeurs de $a_i$ diffèrent. Attention : une « configuration initiale » désigne ici la configuration avant l'ajout des $k$ pierres.

Entrée

Lisez les données dans le fichier stone.in.

Ce problème comporte plusieurs jeux de données. La première ligne contient un entier positif $T$, leur nombre. Les jeux de données suivent dans l'ordre.

Pour chaque jeu de données, la première ligne contient deux entiers $n,k$, le nombre de tas et le nombre de pierres à ajouter. Chacune des $n$ lignes suivantes contient deux entiers non négatifs $l_i,r_i$, les limites du nombre initial de pierres du tas correspondant.

Sortie

Écrivez la sortie dans le fichier stone.out.

Pour chaque jeu de données, affichez sur une ligne un entier représentant le nombre de configurations permettant de gagner, modulo $10^9+7$.

Exemples

Entrée 1

1
4 1
0 1
0 1
0 1
0 1

Sortie 1

14

Remarque

Il existe $2^4=16$ configurations initiales possibles. On peut montrer que toutes permettent de gagner sauf $(0,0,0,0)$ et $(1,0,0,1)$. Par exemple, à partir de $(1,0,1,0)$, vous pouvez ajouter la pierre de votre main au deuxième tas pour obtenir $(1,1,1,0)$, puis appliquer une fois l'opération 2 à l'intervalle $[1,3]$.

Exemple 2

Voir les fichiers stone/stone2.in et stone/stone2.ans dans le répertoire des candidats.

Exemple 3

Voir les fichiers stone/stone3.in et stone/stone3.ans dans le répertoire des candidats.

Exemple 4

Voir les fichiers stone/stone4.in et stone/stone4.ans dans le répertoire des candidats.

Contraintes

Pour $100\%$ des données, $T\le10$, $3\le n\le1000$, $0\le l_i\le r_i\le10^9$, $0\le k\le100$.