Security Badge

You are in charge of security for a large building with $n$ rooms and $m$ doors between the rooms. Rooms are numbered 1 to $n$, and doors are numbered 1 to $m$.

Door $i$ opens from room $a_i$ to room $b_i$ and not the other way around. Every door has a security code given as a range of integers $[c_i, d_i]$.

There are $k$ employees in the building. Each employee carries a security badge, and the badge IDs are distinct integers between 1 and $k$. An employee whose badge ID is $x$ goes through door $i$ only when $c_i \le x \le d_i$.

Your boss wants a quick check of the building's security. Given $s$ and $t$, how many employees can get from room $s$ to room $t$?

The first line contains three space separated integers $n$, $m$, and $k$ ($2 \le n \le 1\,000$, $1 \le m \le 5\,000$, $1 \le k \le 10^9$).

The second line contains two space separated integers $s$ and $t$ ($1 \le s, t \le n$, $s \ne t$).

Each of the next $m$ lines contains four space separated integers $a_i$, $b_i$, $c_i$, and $d_i$ describing door $i$ ($1 \le a_i, b_i \le n$, $1 \le c_i \le d_i \le k$, $a_i \ne b_i$).

For any two rooms $a$ and $b$ there is at most one door from $a$ to $b$, but a door from $a$ to $b$ and a door from $b$ to $a$ may both exist.

Print, on a single line, the number of employees who can reach room $t$ starting from room $s$.