없는 등수 찾기

모의고사에 $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등이 없는 경우를 세면 다음과 같다.

• 1번과 2번이 2점: 9가지
• 1번과 2번이 3점, 3번이 4점 이상: 6가지
• 1번과 3번이 3점, 2번이 4점: 3가지
• 1번, 2번, 3번이 모두 3점: 3가지

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