무당벌레

Albert는 무당벌레의 길 찾기 능력을 연구한다. 실험을 위해 격자 모양의 미로를 만들고, 무당벌레가 어떤 칸들을 거쳐 미로를 탈출하는지 조사한다. 미로는 $R$행 $C+1$열, 총 $R \times (C+1)$개의 칸으로 이루어진다. 그중 $N$개의 칸에는 장애물이 설치되어 있어서 무당벌레가 방문하거나 지나갈 수 없다. 편의상 $i$번째 장애물은 $x_i$행 $y_i$열에 있다고 하자. 또한 $(r, c)$는 $r$행 $c$열의 칸을 뜻한다.

Albert는 무당벌레를 $I$행 1열의 칸에 풀어 놓는다. 무당벌레는 다음 규칙에 따라 이동한다.

• $r > 1$인 $(r, c)$ 칸에서는 $(r-1, c)$ 칸으로 위쪽 이동할 수 있다. $r = 1$이면 위쪽이 막혀 있어 이동할 수 없다.
• $r < R$인 $(r, c)$ 칸에서는 $(r+1, c)$ 칸으로 아래쪽 이동할 수 있다. $r = R$이면 아래쪽이 막혀 있어 이동할 수 없다.
• $(r, c)$ 칸에서는 $(r, c+1)$ 칸으로 오른쪽 이동할 수 있다. $c = C$이면, 즉 $C$열에서 $C+1$열로 이동하면 미로를 탈출한 것으로 보고 실험을 마친다.
• 요컨대 마지막 열에서 탈출하는 경우를 빼면 위, 아래, 오른쪽으로 자유롭게 움직일 수 있고 왼쪽으로는 움직일 수 없다.

아래 그림은 $R = 3$, $C = 2$, $N = 2$, $x = [3, 3]$, $y = [1, 2]$, $I = 1$인 경우를 보여준다. "x"로 표시된 두 칸에는 장애물이 있고, 무당벌레는 $(I, 1) = (1, 1)$ 칸에서 출발한다. $C$열에서 오른쪽으로 이동해 탈출하면 그림의 "#"로 표시된 칸 중 하나에 도달한다. 편의상 무당벌레가 $c$열에 처음 도달한 행 번호를 $F_c$라고 하자. 항상 $F_1 = I$이다.

아래 그림은 무당벌레가 $(1, 3)$ 칸에 도달하며 탈출한 경로 중 세 가지를 보여준다. 편의상 무당벌레가 지나친 네 개의 칸을 A, B, C, D로 표시했다.

• 경로 1: A -> B -> D -> C -> 탈출. 이때 $F = [1, 2, 1]$이다.
• 경로 2: A -> B -> A -> B -> D -> C -> D -> C -> 탈출. 이때 $F = [1, 2, 1]$이다.
• 경로 3: A -> B -> A -> B -> A -> C -> D -> C -> 탈출. 이때 $F = [1, 1, 1]$이다.

Albert의 실험 장치는 무당벌레가 방문한 칸과 각 열에서 처음 방문한 칸은 기록할 수 있다. 하지만 같은 칸을 몇 번 방문했는지, 칸을 어떤 순서로 방문했는지는 측정하지 못한다. 그래서 위의 세 경로 중 경로 1과 경로 2는 구분할 수 없다. 두 경로 모두 A, B, C, D 네 칸을 방문했고 $F$ 값도 같기 때문이다. 경로 3은 방문한 칸은 같지만 $F_2$ 값이 달라서 다른 두 경로와 구분된다.

위 미로에서 무당벌레가 탈출하는 방법은 실험 장치가 구분할 수 있는 기준으로 아래 그림과 같이 9가지다. 그림에서 "x"는 장애물, "*"는 해당 열에서 무당벌레가 처음 방문한 칸을 뜻한다. 각 탈출 방법에서 방문한 칸의 집합을 $S$라고 하자.

• 위쪽 줄, 왼쪽부터 순서대로
  • $S = \{ (1, 1), (1, 2), (1, 3) \}$, $F = [1, 1, 1]$. 예를 들어 (1, 1) -> (1, 2) -> (1, 3) 순으로 이동하여 탈출한다.
  • $S = \{ (1, 1), (1, 2), (2, 2), (1, 3) \}$, $F = [1, 1, 1]$. 예를 들어 (1, 1) -> (1, 2) -> (2, 2) -> (1, 2) -> (1, 3) 순으로 이동하여 탈출한다.
  • $S = \{ (1, 1), (2, 1), (1, 2), (1, 3) \}$, $F = [1, 1, 1]$. 예를 들어 (1, 1) -> (2, 1) -> (1, 1) -> (1, 2) -> (1, 3) 순으로 이동하여 탈출한다.
  • $S = \{ (1, 1), (2, 1), (1, 2), (2, 2), (1, 3) \}$, $F = [1, 1, 1]$. 예를 들어 (1, 1) -> (2, 1) -> (1, 1) -> (1, 2) -> (2, 2) -> (1, 2) -> (1, 3) 순으로 이동하여 탈출한다.
  • $S = \{ (1, 1), (2, 1), (1, 2), (2, 2), (1, 3) \}$, $F = [1, 2, 1]$. 예를 들어 (1, 1) -> (2, 1) -> (2, 2) -> (1, 2) -> (1, 3) 순으로 이동하여 탈출한다.
• 아래쪽 줄, 왼쪽부터 순서대로
  • $S = \{ (1, 1), (1, 2), (2, 2), (2, 3) \}$, $F = [1, 1, 2]$. 예를 들어 (1, 1) -> (1, 2) -> (2, 2) -> (2, 3) 순으로 이동하여 탈출한다.
  • $S = \{ (1, 1), (2, 1), (2, 2), (2, 3) \}$, $F = [1, 2, 2]$. 예를 들어 (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) 순으로 이동하여 탈출한다.
  • $S = \{ (1, 1), (2, 1), (1, 2), (2, 2), (2, 3) \}$, $F = [1, 1, 2]$. 예를 들어 (1, 1) -> (2, 1) -> (1, 1) -> (1, 2) -> (2, 2) -> (2, 3) 순으로 이동하여 탈출한다.
  • $S = \{ (1, 1), (2, 1), (1, 2), (2, 2), (2, 3) \}$, $F = [1, 2, 2]$. 예를 들어 (1, 1) -> (2, 1) -> (2, 2) -> (1, 2) -> (2, 2) -> (2, 3) 순으로 이동하여 탈출한다.

이 미로에서 무당벌레가 탈출하는 서로 다른 방법은 위의 9가지뿐이다.

Albert는 두 탈출 경로에서 방문한 칸의 집합 $S$가 같고, 각 열에서 처음 방문한 칸 $F$도 같으면 같은 탈출 방법으로 본다. 마지막에 어떤 칸을 통해 탈출했는지가 중요하므로, $(r, C+1)$ 칸에 도달하며 탈출하는 방법의 수를 $A_r$이라 하고 배열 $A$를 구하려 한다. 위 미로의 경우 $A = [5, 4, 0]$이다.

입력으로 $R$, $C$, $N$, $I$와 배열 $x$, $y$가 주어질 때 $A_1, A_2, \dots, A_R$을 구하라.

입력의 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $R$, $C$, $N$, $I$가 공백으로 구분되어 주어진다. 다음 $N$개의 줄에는 각 줄마다 정수 2개가 공백으로 구분되어 주어지며, $i$번째 줄의 두 정수는 $i$번째 장애물의 위치 $x_i$, $y_i$이다.

각 테스트 케이스의 정답 $A_1, A_2, \dots, A_R$을 공백으로 구분하여 한 줄에 출력한다. 값이 매우 클 수 있으므로 각 값을 $10^9 + 7$로 나눈 나머지를 출력한다.

• $1 \le T \le 30$
• $1 \le R \le 20$
• $1 \le C \le 10^6$
• $1 \le N \le 250$
• $1 \le I \le R$
• $1 \le i \le N$인 모든 $i$에 대하여
  • $1 \le x_i \le R$
  • $1 \le y_i \le C$
  • $(x_i, y_i) \neq (I, 1)$ (무당벌레가 출발하는 칸에는 장애물이 없다)
  • $(x_i, y_i)$는 서로 다르다