시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 32 MB 1 1 1 100.000%

문제

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

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

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

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

입력

첫 번째 줄에 모의고사를 보는 사람의 수 N과 만점 M이 주어집니다. 두 번째 줄부터 N개의 줄에는 각 사람의 점수의 범위 Ak, Bk가 주어집니다. 마지막 줄에는 근우가 좋아하는 수 R이 주어집니다. (1 ≤ N ≤ 250, 1 ≤ M ≤ 400)

출력

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

예제 입력

4 6
1 3
2 4
3 5
4 6
4

예제 출력

21

힌트

각 사람들은 Ak점 이상 Bk점 이하의 점수를 받는다고 가정합니다.

아래 예제의 경우 각 사람은 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가지입니다.