돌 제거

$n$개의 더미가 일렬로 놓여 있고, $i$번째 더미에는 $a_i$개의 돌이 있다. 다음 두 연산으로 모든 돌을 제거해야 한다.

• 더미 하나를 골라 그 더미에서 돌을 2개 이상 제거한다.
• $r - l \geq 2$를 만족하는 연속 구간 $[l, r]$을 고르고, 구간에 속한 모든 더미에서 돌을 1개씩 제거한다.

두 연산은 순서에 상관없이 원하는 횟수만큼 수행할 수 있으며, 더 이상 수행할 수 없을 때까지 진행한다. 모든 돌을 제거하면 이긴다.

게임을 시작하기 전에 숨겨진 돌 $k$개를 한 더미 또는 여러 더미에 넣어야 한다. $k$개를 어떻게 나누어 넣을지는 자유롭게 정할 수 있다. 각 더미 $i$의 초기 돌 개수 $a_i$는 범위 $[l_i, r_i]$ 안의 정수 중 하나다. 이기는 초기 상태의 개수를 $10^9+7$로 나눈 나머지를 구한다. 적어도 하나의 $a_i$가 다르면 두 상태는 서로 다른 상태다. 여기서 초기 상태란 $k$개의 돌을 넣기 전의 상태를 뜻한다.

첫 줄에 테스트케이스의 개수 $T$가 주어진다. 각 테스트케이스의 첫 줄에는 $n$과 $k$가 주어진다. 이어서 $n$개의 줄에 각 더미의 범위 $l_i$와 $r_i$가 주어진다.

각 테스트케이스마다 이기는 초기 상태의 개수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.

• $T \leq 10$
• $3 \leq n \leq 1000$
• $0 \leq l_i \leq r_i \leq 10^9$
• $0 \leq k \leq 100$