무당벌레

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

Albert는 우선 무당벌레를 $I$ 행 1열의 칸에 풀어두는데, 무당벌레는 아래와 같은 규칙에 따라 이동할 수 있다.

• 임의의 $(r, c)$ 칸에서 $r \gt 1$ 인 경우 $(r-1, c)$ 칸으로 (위쪽 방향으로) 이동할 수 있다. $r = 1$ 인 경우, 위쪽 방향은 막혀있어서 이동할 수 없다.
• 임의의 $(r, c)$ 칸에서 $r \lt R$ 인 경우 $(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$ 값이 다르다). Albert는 무당벌레가 몇 가지 다른 방법으로 미로를 탈출할 수 있는지 궁금한데, 특히 실험장치가 구분할 수 있는 탈출 방법의 수가 궁금하다.

위 예제의 경우 아래와 같은 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)$ 는 고유하다