테스트 데이터 분석

길이 $N$인 정수 배열 $X$에서, 연속한 부분 배열 중 원소 합이 최대인 값을 최대 부분 배열 합이라 부른다.

각 위치 $i$는 $A_i \leq X_i \leq B_i$를 만족해야 한다. 최대 부분 배열 합이 정확히 $D$가 되는 서로 다른 배열 $X$의 개수를 $1{,}000{,}000{,}007$로 나눈 나머지를 출력하라.

첫 줄에 테스트 케이스 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$과 $D$ ($1 \leq N \leq 1000$, $-1000 \leq D \leq 1000$)가 공백으로 구분되어 있다.

다음 $N$줄의 $i$번째 줄에는 $A_i$, $B_i$ ($-1000 \leq A_i \leq B_i \leq 1000$)가 주어진다.

각 테스트 케이스마다 조건을 만족하는 배열의 개수를 $1{,}000{,}000{,}007$로 나눈 나머지를 한 줄에 출력한다.

$N = 3$, $D = 3$, 모든 구간이 $[-1, 2]$일 때 답은 12이다.