보안 사원증

당신은 방 $n$개와 방 사이를 잇는 문 $m$개로 이루어진 큰 건물의 보안을 맡고 있다. 방에는 1번부터 $n$번까지, 문에는 1번부터 $m$번까지 번호가 붙어 있다.

$i$번 문은 $a_i$번 방에서 $b_i$번 방으로만 열리고 반대 방향으로는 열리지 않는다. 문마다 보안 코드가 있고, 이 코드는 정수 구간 $[c_i, d_i]$로 나타낸다.

건물에서는 직원 $k$명이 일한다. 각 직원의 사원증 번호는 1 이상 $k$ 이하의 정수이고 서로 다르다. 사원증 번호가 $x$인 직원은 $c_i \le x \le d_i$일 때만 $i$번 문을 통과한다.

상사가 건물의 보안 상태를 빠르게 확인하려 한다. $s$와 $t$가 주어질 때, $s$번 방에서 출발해 $t$번 방까지 갈 수 있는 직원은 몇 명인가?

첫째 줄에 정수 $n$, $m$, $k$가 공백으로 구분되어 주어진다. ($2 \le n \le 1\,000$, $1 \le m \le 5\,000$, $1 \le k \le 10^9$)

둘째 줄에 정수 $s$와 $t$가 공백으로 구분되어 주어진다. ($1 \le s, t \le n$, $s \ne t$)

이어지는 $m$개의 줄에는 $i$번 문을 나타내는 정수 $a_i$, $b_i$, $c_i$, $d_i$가 공백으로 구분되어 주어진다. ($1 \le a_i, b_i \le n$, $1 \le c_i \le d_i \le k$, $a_i \ne b_i$)

서로 다른 두 방 $a$, $b$에 대해 $a$에서 $b$로 가는 문은 많아야 하나다. 다만 $a$에서 $b$로 가는 문과 $b$에서 $a$로 가는 문이 둘 다 있을 수는 있다.

$s$번 방에서 출발해 $t$번 방까지 갈 수 있는 직원 수를 한 줄에 출력한다.