케밥 하우스

바흐탕 부메랑은 패스트푸드 체인점 케밥 하우스에서 케밥을 만든다. 케밥 하나에는 여러 재료가 들어간다.

오늘 아침 바흐탕은 케밥 $n$개를 만들라는 주문을 받았다. 첫 번째 케밥에 재료 $q_1$개, 두 번째 케밥에 재료 $q_2$개를 넣는 식으로 순서대로 만든다. 재료 하나를 넣는 데 정확히 1초가 걸리므로 $i$번째 케밥을 만드는 데는 $q_i$초가 걸리고, 하나를 끝내면 곧바로 다음 케밥으로 넘어간다. 그래서 작업 전체가 $q_1 + q_2 + \dots + q_n$초 동안 끊기지 않고 이어지며, 시작한 순간부터 1초, 2초, 3초와 같이 번호를 매긴다.

일하는 동안 바흐탕은 아끼는 부메랑을 떠올리며 공상에 잠기곤 한다. 공상 한 번은 정확히 1초 동안 이어지고, 그 1초에는 재료 넣기를 잊는다. 다만 어떤 연속한 $t+1$초 안에서도 공상을 두 번 하지는 않는다. 즉 공상한 두 초의 번호 차이는 항상 $t+1$ 이상이다.

공상 탓에 케밥에 들어간 재료가 원래 넣으려던 수보다 적을 수 있다. $i$번째 손님은 $i$번째 케밥에 재료가 $x_i$개 이상 들어 있으면 만족한다.

모든 손님이 만족하도록 공상할 초를 고르는 방법의 수를 $10^9+7$로 나눈 나머지를 구하여라. 공상한 초의 집합이 다르면 서로 다른 방법으로 센다.

첫째 줄에 케밥의 개수 $n$과 공상 사이의 최소 간격을 정하는 값 $t$가 주어진다. ($1 \le n \le 1000$, $0 \le t \le 100$)

다음 $n$개 줄의 $i$번째 줄에는 $i$번째 케밥에 넣으려는 재료의 수 $q_i$와 $i$번째 손님을 만족시키는 데 필요한 최소 재료 수 $x_i$가 주어진다. ($1 \le q_i \le 250$, $0 \le x_i \le q_i$)

모든 손님이 만족하도록 공상할 초를 고르는 방법의 수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.