Find the missing rank

$N$ people take a mock exam whose maximum score is $M$. Keunwoo roughly knows how strong they are, so he expects person $k$ to score at least $A_k$ and at most $B_k$.

The exam is graded on a curve, so once it is over every person gets a rank between $1$ and $N$. A person's rank is the number of people with a strictly higher score, plus $1$.

If $N=5$ and $M=10$ and the five people score 6, 5, 3, 9 and 5, their ranks are 2, 3, 5, 1 and 3 in that order. Because of the tie, nobody gets rank 4.

For his favourite number $R$, Keunwoo wants to know how many outcomes leave rank $R$ empty. An outcome gives every person one score inside their own range, and two outcomes are different if at least one person's score is different.

The first line contains the number of people $N$ and the maximum score $M$. Each of the next $N$ lines contains the score range $A_k$ and $B_k$ of person $k$. The last line contains Keunwoo's favourite number $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$

Print the number of outcomes in which nobody gets rank $R$, modulo 1,000,000,007 ($10^9+7$).

Take $N=4$, $M=6$, the four ranges 1 to 3, 2 to 4, 3 to 5 and 4 to 6, and $R=4$. Splitting by the scores of people 1, 2 and 3, the outcomes without a rank 4 are:

• people 1 and 2 score 2: 9 outcomes
• people 1 and 2 score 3 and person 3 scores at least 4: 6 outcomes
• people 1 and 3 score 3 and person 2 scores 4: 3 outcomes
• people 1, 2 and 3 all score 3: 3 outcomes

So 21 outcomes leave rank 4 empty.