없는 등수 찾기

시간 제한2초메모리 제한32 MB

요약

각 사람이 주어진 점수 구간 안에서 점수를 받을 때 동점자 순위로 R위를 받는 사람이 없는 경우의 수를 셉니다.

문제

모의고사에 $N$ 명이 참가하고 만점은 $M$ 점이다. 근우는 참가자의 실력을 대강 알고 있어서, $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$ 개의 줄에는 $k$ 번째 사람의 점수 범위 $A_k$ 와 $B_k$ 가 주어진다. 마지막 줄에는 근우가 좋아하는 수 $R$ 이 주어진다.

$1 \le N \le 250$ , $1 \le M \le 400$ , $0 \le A_k \le B_k \le M$ , $1 \le R \le N$

$R$ 등을 받은 사람이 없는 경우의 수를 1,000,000,007( $10^9+7$ )로 나눈 나머지를 출력한다.

$N=4$ , $M=6$ 이고 네 사람의 점수 범위가 차례대로 1점 이상 3점 이하, 2점 이상 4점 이하, 3점 이상 5점 이하, 4점 이상 6점 이하이며 $R=4$ 인 경우를 보자. 1번, 2번, 3번 사람의 점수로 나누어 4등이 없는 경우를 세면 다음과 같다.

그래서 4등이 없는 경우는 모두 21가지다.