없는 등수 찾기 Batch 컴파일 명령

이번 GENIUSainta.com의 모의고사에는 $N$명의 사람들이 참가할 것이고, 만점이 $M$점입니다. 근우는 이 모의고사를 보는 $N$명의 사람들의 실력을 대충 알기 때문에, $k$번째 사람은 $A_{k}$점 이상 $B_{k}$점 이하의 점수를 받을 것이라고 추측하고 있습니다.

모의고사는 상대평가로 이루어지기 때문에 모의고사가 끝나면 각 사람들은 1 이상 $N$ 이하의 등수를 갖게 됩니다. 여기서 각 사람의 등수는 자기보다 점수가 높은 사람의 수에 1을 더한 값입니다.

만약 $N=5, M=10$인 대회에서 사람들이 각각 6점, 5점, 3점, 9점, 5점을 받았다면 그들의 등수는 각각 2등, 3등, 5등, 1등, 3등입니다. 동점자가 있기 때문에 4등을 받은 사람은 없습니다.

근우는 자신이 좋아하는 숫자 $R$에 대해서, $R$등을 받은 사람이 없는 경우가 얼마나 많은지 알고자 합니다.

입력 형식

첫 번째 줄에 모의고사를 보는 사람의 수 $N$과 만점 $M$이 주어집니다. 두 번째 줄부터 $N$개의 줄에는 각 사람의 점수의 범위 $A_k$, $B_{k}$가 주어집니다. 마지막 줄에는 근우가 좋아하는 수 $R$이 주어집니다.

출력 형식

모의고사에서 $R$등을 받는 사람이 없는 경우의 수를 1,000,000,007 (10억 7)로 나눈 나머지를 출력합니다.

참고

각 사람들은 $A_{k}$점 이상 $B_{k}$점 이하의 점수를 받는다고 가정합니다.

아래 예제의 경우 각 사람은 1~3점, 2~4점, 3~5점, 4~6점을 받습니다. 1, 2, 3번 사람의 점수에 따라 4등이 없는 경우의 수를 세면 다음과 같습니다.

• 1, 2번 사람이 2점 : 9가지
• 1, 2번 사람이 3점, 3번 사람이 4점 이상 : 6가지
• 1, 3번 사람이 3점, 2번 사람이 4점 : 3가지
• 1, 2, 3번 사람이 3점 : 3가지

따라서 4등이 없는 경우는 총 21가지입니다.

서브태스크

모든 서브태스크에 대해

• $0 \le A_{k} \le B_{k} \le M$
• $1 \le R \le N$

서브태스크 1 (10점)

• $1 \le N \le 12$
• $1 \le M \le 100$
• $R = 1$

서브태스크 2 (20점)

• $1 \le N \le 12$
• $1 \le M \le 100$
• $0 \le B_{k} - A_{k} \le 2$

서브태스크 3 (30점)

• $2 \le N \le 250$
• $1 \le M \le 400$
• $R = 2$

서브태스크 4 (40점)

• $1 \le N \le 250$
• $1 \le M \le 400$

입력과 출력의 예