Coder's High 2014의 예비소집을 위해 명우는 아래와 같은 간단한 문제를 준비했다.</p>

크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.

여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max_{1 ≤ i ≤  j ≤ N} (X[i]+...+X[j])를 구하자.

명우는 데이터를 만들 때 각 X_i를 어떤 두 정수 A_i, B_i에 대해 A_i ≤ X_i ≤ B_i을 만족하게 만들기로 정했다. N도 정한 명우는 이제 데이터를 만들려고 하였는데, 문득 답이 D가 되는 서로 다른 입력데이터의 개수가 몇 개 일지 궁금해졌다.

입력 형식

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.</p>

각 테스트 케이스의 첫 번째 줄에는 두 정수 N (1 ≤ N ≤ 1,000)과 D (-1,000 ≤ D ≤ 1,000)가 공백으로 구분되어 주어진다.

다음 N개의 줄의 i번째 줄에는 A_i, B_i (-1,000 ≤ A_i ≤ B_i ≤ 1,000)가 공백으로 구분되어 주어진다.

출력 형식

각 테스트 케이스마다 한 줄에 답이 D 가 되는 입력의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력

2
3 3
-1 2
-1 2
-1 2
5 3
-1 5
-2 3
-4 5
-2 3
-2 6

예제 출력

12
1897

힌트

첫 번째 예제에서 답이 3인 X는 아래의 12개이다.</p>

(-1,1,2)  (-1,2,1)  (0,1,2)  (0,2,1)  (1,0,2)  (1,1,1)

(1,2,-1)  (1,2,0)  (2,-1,2)  (2,0,1)  (2,1,-1)  (2,1,0)