cho.sh

Race for the Galaxy

아직 제출이 없습니다시간 제한4초메모리 제한1024 MB

문제

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

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

  • SS번째 가로선과 S+1S+1번째 가로선 사이에 진흙밭이 생겨서, 세로선 NN개에 해당하는 구간이 진흙으로 뒤덮였습니다. 즉, NN개의 세로선 번호 t_1,t_2,⋯ ,t_Nt\_1, t\_2, \cdots, t\_N에 대해 (S,t_i)(S, t\_i)와 (S+1,t_i)(S+1, t\_i)를 잇는 세로 구간에는 진흙이 있습니다.
  • MM개의 물웅덩이가 생겼습니다. 그중 jj번째 물웅덩이는 (x_j,y_j)(x\_j, y\_j)에 있습니다.

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

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

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

  • ii번째 선수의 경주로는 (1,a_i)(1, a\_i)에서 시작해서 (R,b_i)(R, b\_i)로 끝나는 서로 인접한 교차점의 수열입니다. (1≤i≤N)(1 \le i \le N)

    • 두 교차점 (r_1,c_1)(r\_1, c\_1)과 (r_2,c_2)(r\_2, c\_2)가 서로 인접한다는 것은 수식 ∣r_1−r_2∣+∣c_1−c_2∣=1|r\_1-r\_2|+|c\_1-c\_2|=1을 만족함을 뜻합니다.

  • 수열에 속한 모든 교차점 (r,c)(r, c)에 대해 1≤r≤R,1≤c≤C1 \le r \le R, 1 \le c \le C여야 합니다.

  • (x_j,y_j)(x\_j, y\_j)는 수열에 포함될 수 없습니다. (1≤j≤M1 \le j \le M)

  • 1<r≤R,1≤c≤C1 < r \le R, 1 \le c \le C인 (r,c)(r, c)의 다음 원소가 (r−1,c)(r-1, c)이면 안 됩니다.

  • 1≤r≤R,1≤c<C1 \le r \le R, 1 \le c < C인 r,cr, c에 대해,

    • rr이 홀수이면 (r,c)(r, c)의 다음 원소가 (r,c+1)(r, c+1)이면 안 됩니다.
    • rr이 짝수이면 (r,c+1)(r, c+1)의 다음 원소가 (r,c)(r, c)이면 안 됩니다.

  • 한 교차점은 최대 하나의 수열에만 포함됩니다.

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

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

입력

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

둘째 줄에 a_1,a_2,⋯ ,a_Na\_1, a\_2, \cdots, a\_N이 공백으로 구분되어 주어집니다. (1≤a_1<a_2<⋯<a_N≤C)(1 \le a\_1 < a\_2 < \cdots < a\_N \le C)

셋째 줄에 b_1,b_2,⋯ ,b_Nb\_1, b\_2, \cdots, b\_N이 공백으로 구분되어 주어집니다. (1≤b_1<b_2<⋯<b_N≤C)(1 \le b\_1 < b\_2 < \cdots < b\_N \le C)

넷째 줄에 t_1,t_2,⋯ ,t_Nt\_1, t\_2, \cdots, t\_N이 공백으로 구분되어 주어집니다. (1≤t_1<t_2<⋯<t_N≤C)(1 \le t\_1 < t\_2 < \cdots < t\_N \le C)

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

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

출력

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