Estás a jogar um pequeno jogo chamado «Remover pedras».

Há $n$ montes de pedras dispostos numa fila. O $i$-ésimo monte contém $a_i$ pedras. A tua tarefa é remover todas as pedras através das operações seguintes:

• Operação um: escolher um monte e remover pelo menos $2$ pedras desse monte;
• Operação dois: escolher um intervalo de índices consecutivos $[l,r]$, com $1\le l\le r\le n$ e $r-l\ge 2$, e remover exatamente $1$ pedra de cada monte nesse intervalo.

Podes realizar estas duas operações um número arbitrário de vezes e em qualquer ordem, até deixar de ser possível realizar operações. Se conseguires remover todas as pedras, ganhas.

Talvez já tenhas começado a calcular coisas como «quantas sequências de operações essencialmente diferentes existem», mas, ao jogares, descobriste que estás sempre a perder. Por isso, decidiste recorrer a um pequeno truque: no início do jogo, escondes $k$ pedras na mão e, antes de realizares qualquer operação, podes e tens de colocar essas pedras num ou em vários montes. Esperas que isso aumente as tuas hipóteses de ganhar, embora saibas que também pode fazer-te perder um jogo que originalmente poderias ganhar.

Agora podes escolher livremente uma configuração inicial para jogar. Mais precisamente, cada $a_i$ pode ser qualquer inteiro no intervalo $[l_i,r_i]$. Queres calcular para quantas configurações iniciais existe pelo menos uma estratégia que te permita ganhar. Como a resposta é muito grande, só precisas de apresentar o seu valor módulo $10^9+7$. Duas configurações iniciais são diferentes se e somente se existir pelo menos um $1\le i\le n$ para o qual os respetivos valores de $a_i$ sejam diferentes. Repara que «configuração inicial» se refere à configuração antes de adicionares as $k$ pedras.

Entrada

Lê os dados do ficheiro stone.in.

Este problema tem vários casos de teste. A primeira linha contém um inteiro positivo $T$, que representa o número de casos de teste. Seguem-se os casos de teste, por ordem.

Para cada caso, a primeira linha contém dois inteiros $n,k$, que representam, respetivamente, o número de montes e o número de pedras a adicionar. Seguem-se $n$ linhas, cada uma com dois inteiros não negativos $l_i,r_i$, que indicam o intervalo do número inicial de pedras em cada monte.

Saída

Escreve a saída no ficheiro stone.out.

Para cada caso de teste, apresenta uma linha com um inteiro: o número de configurações nas quais é possível ganhar, módulo $10^9+7$.

Exemplos

Entrada 1

1
4 1
0 1
0 1
0 1
0 1

Saída 1

14

Explicação do exemplo 1

Existem $2^4=16$ configurações iniciais possíveis. Pode provar-se que, exceto nas configurações $(0\ 0\ 0\ 0)$ e $(1\ 0\ 0\ 1)$, nas quais não é possível ganhar, todas as outras admitem uma estratégia vencedora. Por exemplo, na configuração inicial $(1\ 0\ 1\ 0)$, podes colocar a pedra que tens na mão no segundo monte, obtendo a configuração $(1\ 1\ 1\ 0)$, e depois aplicar uma vez a operação dois ao intervalo $[1,3]$.

Exemplo 2

Consulta os ficheiros stone/stone2.in e stone/stone2.ans no diretório dos concorrentes.

Exemplo 3

Consulta os ficheiros stone/stone3.in e stone/stone3.ans no diretório dos concorrentes.

Exemplo 4

Consulta os ficheiros stone/stone4.in e stone/stone4.ans no diretório dos concorrentes.

Restrições

Para $100\%$ dos dados, garante-se que $T\le 10$, $3\le n\le 1000$, $0\le l_i\le r_i\le 10^9$, $0\le k\le 100$.