Race for the Galaxy

A school playground has a large grid with $R$ horizontal lines and $C$ vertical lines. The intersection of the $r$-th horizontal line from the top and the $c$-th vertical line from the left is called $(r, c)$.

Heavy rain yesterday created several obstacles on the playground.

• Between the $S$-th and $(S+1)$-th horizontal lines there is a muddy area covering the segments of $N$ vertical lines. That is, for each vertical line number $t_1, t_2, \cdots, t_N$, the vertical segment connecting $(S, t_i)$ and $(S+1, t_i)$ is covered in mud.
• There are $M$ puddles. The $j$-th puddle is at $(x_j, y_j)$.

Hyea plans to draw $N$ running tracks on the playground, one for each of $N$ runners, for a race at the sports day. The event is meant to build harmony more than to record times, so the race has several rules.

• The goal of each track is to start at the starting point on the first horizontal line and finish at the ending point on the last horizontal line. Each runner has a fixed start and end. The $i$-th runner starts at $(1, a_i)$ and must finish at $(R, b_i)$. Here $a_1 < a_2 < \cdots < a_N$ and $b_1 < b_2 < \cdots < b_N$.
• Runners must run along the horizontal and vertical lines of the grid. They cannot leave the grid, move in a direction that is neither horizontal nor vertical, or change direction anywhere except at an intersection.
• When moving along a vertical line, a runner must move downward.
• When moving along a horizontal line, a runner must move left on an odd-numbered horizontal line and must move right on an even-numbered horizontal line.
• Puddles are dangerous because the ground is dug out there, so no track may pass through an intersection with a puddle.
• Two runners colliding is also dangerous, so no two tracks may share an intersection.

The rules stated more precisely:

• The track of the $i$-th runner is a sequence of intersections that starts at $(1, a_i)$, ends at $(R, b_i)$, and in which consecutive intersections are adjacent. ($1 \le i \le N$) Two intersections $(r_1, c_1)$ and $(r_2, c_2)$ are adjacent when $|r_1-r_2|+|c_1-c_2|=1$.
• Every intersection $(r, c)$ in a sequence must satisfy $1 \le r \le R$ and $1 \le c \le C$.
• $(x_j, y_j)$ cannot appear in any sequence. ($1 \le j \le M$)
• For $(r, c)$ with $1 < r \le R$ and $1 \le c \le C$, the element after $(r, c)$ cannot be $(r-1, c)$.
• For $r$ and $c$ with $1 \le r \le R$ and $1 \le c < C$: if $r$ is odd, the element after $(r, c)$ cannot be $(r, c+1)$. If $r$ is even, the element after $(r, c+1)$ cannot be $(r, c)$.
• Each intersection belongs to at most one sequence.

Among all ways to draw the tracks under these rules, count the number of ways in which exactly $k$ runners pass through a muddy area, for each $k = 0, 1, \cdots, N$. The numbers can be very large, so print each count modulo the prime $1\,000\,000\,007$ ($=10^9+7$).

• The $i$-th runner passes through a muddy area if there is some $1 \le j \le N$ such that $(S, t_j)$ and $(S+1, t_j)$ appear consecutively in the sequence.

The first line contains $R$, $C$, $N$, $M$, and $S$, separated by spaces. ($3 \le R, C \le 300$; $3 \le N \le C$; $0 \le M \le 300$; $1 \le S < R$)

The second line contains $a_1, a_2, \cdots, a_N$, separated by spaces. ($1 \le a_1 < a_2 < \cdots < a_N \le C$)

The third line contains $b_1, b_2, \cdots, b_N$, separated by spaces. ($1 \le b_1 < b_2 < \cdots < b_N \le C$)

The fourth line contains $t_1, t_2, \cdots, t_N$, separated by spaces. ($1 \le t_1 < t_2 < \cdots < t_N \le C$)

If $M > 0$, each of the next $M$ lines contains $x_j$ and $y_j$, separated by a space. ($1 < x_j < R$; $1 \le y_j \le C$)

All puddle positions are distinct.

Print $N+1$ integers on the first line, separated by spaces. The $(k+1)$-th integer is the number of ways in which exactly $k$ runners pass through a muddy area, modulo $1\,000\,000\,007$ ($=10^9+7$). ($0 \le k \le N$)