25313번 - Race for the Galaxy

혜아의 학교에는 가로선 $R$개와 세로선 $C$개로 이루어진 커다란 격자가 그려진 운동장이 있습니다. 위에서 $r$번째 가로선과 왼쪽에서 $c$번째 세로선이 만나는 교차점을 $(r, c)$라고 합시다.

이 운동장에는, 어제 비가 많이 오는 바람에 여러 장애물이 생겼습니다.

• $S$번째 가로선과 $S+1$번째 가로선 사이에 진흙밭이 생겨서, 세로선 $N$개에 해당하는 구간이 진흙으로 뒤덮였습니다. 즉, $N$개의 세로선 번호 $t_1, t_2, \cdots, t_N$에 대해 $(S, t_i)$와 $(S+1, t_i)$를 잇는 세로 구간에는 진흙이 있습니다.
• $M$개의 물웅덩이가 생겼습니다. 그중 $j$번째 물웅덩이는 $(x_j, y_j)$에 있습니다.

혜아는 운동회에서 열릴 달리기 시합을 위해 운동장에 $N$명의 선수가 달릴 $N$개의 경주로를 그리려고 합니다. 운동회는 기록보다 화합을 위한 행사이기 때문에, 이 경주에도 즐거움을 주기 위한 여러 규칙이 붙어있습니다.

• 경주의 목적은 첫 번째 가로선 위의 출발점에서 출발해 마지막 가로선 위의 도착점으로 도착하는 것으로, 각 선수에게는 출발점과 도착점이 정해져 있습니다. $i$번째 선수는 $(1, a_i)$에서 출발해 $(R, b_i)$에 도착해야 합니다. 이때, $a_1 < a_2 < \cdots < a_N;$ $b_1 < b_2 < \cdots < b_N$을 만족합니다.
• 선수는 반드시 격자의 가로선과 세로선을 따라 달려야 합니다. 즉, 격자를 벗어나거나, 가로 또는 세로가 아닌 방향으로 움직이거나, 두 선의 교차점이 아닌 곳에서 방향을 바꿀 수 없습니다.
• 선수가 세로선을 따라 움직일 때는 반드시 아래 방향으로 움직여야 합니다.
• 선수가 가로선을 따라 움직일 때는 홀수 번째 가로선을 따라 움직인다면 반드시 왼쪽으로, 반대로 짝수 번째 가로선을 따라 움직인다면 반드시 오른쪽으로 움직여야 합니다.
• 물웅덩이가 있는 곳은 땅이 파여 있어 위험하므로, 어떤 선수의 경주로도 물웅덩이가 있는 교차점을 지나서는 안 됩니다.
• 마찬가지로 두 선수가 서로 부딪히는 것도 위험하므로, 어떤 두 선수의 경주로가 같은 교차점을 공유해서도 안 됩니다.

위 규칙을 좀 더 엄밀하게 표현하면 다음과 같습니다.

• $i$번째 선수의 경주로는 $(1, a_i)$에서 시작해서 $(R, b_i)$로 끝나는 서로 인접한 교차점의 수열입니다. $(1 \le i \le N)$
  • 두 교차점 $(r_1, c_1)$과 $(r_2, c_2)$가 서로 인접한다는 것은 수식 $|r_1-r_2|+|c_1-c_2|=1$을 만족함을 뜻합니다.
• 수열에 속한 모든 교차점 $(r, c)$에 대해 $1 \le r \le R, 1 \le c \le C$여야 합니다.
• $(x_j, y_j)$는 수열에 포함될 수 없습니다. ($1 \le j \le M$)
• $1 < r \le R, 1 \le c \le C$인 $(r, c)$의 다음 원소가 $(r-1, c)$이면 안 됩니다.
• $1 \le r \le R, 1 \le c < C$인 $r, c$에 대해,
  • $r$이 홀수이면 $(r, c)$의 다음 원소가 $(r, c+1)$이면 안 됩니다.
  • $r$이 짝수이면 $(r, c+1)$의 다음 원소가 $(r, c)$이면 안 됩니다.
• 한 교차점은 최대 하나의 수열에만 포함됩니다.

위 규칙을 만족하며 경주로를 그리는 모든 방법 중, $k$명의 선수가 진흙으로 덮인 구간을 지나게 되는 경우의 수를 $k = 0, 1, \cdots, N$에 대해 구해 주세요. 단, 수가 매우 클 수 있으니 소수인 $1\,000\,000\,007$$(=10^9+7)$로 나눈 나머지를 출력해 주세요.

• $i$번째 선수가 진흙으로 덮인 구간을 지난다는 것은 어떤 $1 \le j \le N$에 대해 수열에 $(S, t_j)$와 $(S+1, t_j)$가 연달아 존재하는 경우가 있다는 뜻입니다.

첫 줄에 $R$, $C$, $N$, $M$, $S$가 공백으로 구분되어 주어집니다. $(3 \le R, C \le 300;$ $3 \le N \le C;$ $0 \le M \le 300;$ $1 \le S < R)$

둘째 줄에 $a_1, a_2, \cdots, a_N$이 공백으로 구분되어 주어집니다. $(1 \le a_1 < a_2 < \cdots < a_N \le C)$

셋째 줄에 $b_1, b_2, \cdots, b_N$이 공백으로 구분되어 주어집니다. $(1 \le b_1 < b_2 < \cdots < b_N \le C)$

넷째 줄에 $t_1, t_2, \cdots, t_N$이 공백으로 구분되어 주어집니다. $(1 \le t_1 < t_2 < \cdots < t_N \le C)$

$M > 0$인 경우 다음 $M$개의 줄의 $j$번째 줄에는 $x_j$와 $y_j$가 공백으로 구분되어 주어집니다. $(1 < x_j < R;$ $1 \le y_j \le C)$

주어지는 모든 물웅덩이의 위치는 서로 다릅니다.

첫 줄에 $N+1$개의 정수를 공백으로 구분하여 출력해 주세요. $k+1$번째 정수는 $k$명의 선수가 진흙으로 덮인 구간을 지나게 되는 경우의 수를 $1\,000\,000\,007$$(=10^9+7)$로 나눈 나머지여야 합니다. $(0 \le k \le N)$