Estás jugando a un pequeño juego llamado «Retirar piedras».

Hay $n$ montones de piedras dispuestos en una fila, y el montón $i$ contiene $a_i$ piedras. Tu tarea es retirar todas las piedras mediante las siguientes operaciones:

• Operación uno: elige un montón y retira de él al menos 2 piedras.
• Operación dos: elige un intervalo de índices consecutivos $[l,r]$ ($1\le l\le r\le n$) que satisfaga $r-l\ge 2$, y retira exactamente 1 piedra de cada montón del intervalo.

Puedes realizar cualquiera de estas dos operaciones tantas veces como quieras y en cualquier orden, hasta que ya no se pueda realizar ninguna. Ganas si al final has retirado todas las piedras.

Quizá ya hayas empezado a calcular cosas como «cuántas formas esencialmente diferentes hay de realizar las operaciones», pero al jugar descubres que siempre pierdes. Por eso decides hacer una pequeña trampa: al empezar el juego, escondes $k$ piedras en la mano y, antes de realizar todas las operaciones, puedes y debes añadirlas a uno o varios montones. Esperas que esto aumente tus probabilidades de ganar, aunque sabes que también podría hacerte perder una partida que originalmente podías ganar.

Ahora puedes elegir libremente una configuración inicial para jugar. Concretamente, cada $a_i$ puede ser cualquier entero del intervalo $[l_i,r_i]$. Quieres calcular cuántas configuraciones iniciales admiten al menos una forma de ganar. Como la respuesta es muy grande, solo debes imprimirla módulo $10^9+7$. Dos configuraciones iniciales son diferentes si y solo si existe al menos un $1\le i\le n$ para el que sus valores de $a_i$ son distintos. Ten en cuenta que aquí «configuración inicial» se refiere a la configuración anterior a añadir las $k$ piedras.

Entrada

Lee los datos del archivo stone.in.

Este problema contiene varios casos de prueba. La primera línea contiene un entero positivo $T$, que indica su número. A continuación se proporciona cada caso en orden.

Para cada caso de prueba, la primera línea contiene dos enteros $n,k$, que indican, respectivamente, el número de montones y el número de piedras añadidas. Las siguientes $n$ líneas contienen dos enteros no negativos $l_i,r_i$ cada una, que indican el rango de la cantidad inicial de piedras de cada montón.

Salida

Escribe la salida en el archivo stone.out.

Para cada caso de prueba, imprime una línea con un entero: el número de configuraciones en las que es posible ganar, módulo $10^9+7$.

Ejemplos

Entrada 1

1
4 1
0 1
0 1
0 1
0 1

Salida 1

14

Nota

Hay $2^4=16$ configuraciones iniciales posibles. Se puede demostrar que todas admiten una estrategia ganadora excepto $(0\ 0\ 0\ 0)$ y $(1\ 0\ 0\ 1)$. Por ejemplo, para la configuración inicial $(1\ 0\ 1\ 0)$, puedes añadir la piedra de tu mano al segundo montón, obteniendo $(1\ 1\ 1\ 0)$, y después realizar una vez la operación dos sobre el intervalo $[1,3]$.

Ejemplo 2

Consulta los archivos stone/stone2.in y stone/stone2.ans del directorio del concursante.

Ejemplo 3

Consulta los archivos stone/stone3.in y stone/stone3.ans del directorio del concursante.

Ejemplo 4

Consulta los archivos stone/stone4.in y stone/stone4.ans del directorio del concursante.

Restricciones

Para el $100\%$ de los datos se garantiza que $T\le 10$, $3\le n\le 1000$, $0\le l_i\le r_i\le 10^9$ y $0\le k\le 100$.