Ladybug

Albert studies how ladybugs find their way. He builds a grid-shaped maze and records which cells the ladybug passes through on its way out. The maze has $R$ rows and $C+1$ columns, for a total of $R \times (C+1)$ cells. $N$ of these cells contain obstacles, which the ladybug cannot visit or pass through. For convenience, the $i$-th obstacle is in row $x_i$ and column $y_i$. Also, $(r, c)$ denotes the cell in row $r$ and column $c$.

Albert releases the ladybug in the cell at row $I$, column 1. The ladybug moves according to these rules.

• From a cell $(r, c)$ with $r > 1$, the ladybug can move up to $(r-1, c)$. If $r = 1$, the upward move is blocked, so it cannot move up.
• From a cell $(r, c)$ with $r < R$, the ladybug can move down to $(r+1, c)$. If $r = R$, the downward move is blocked, so it cannot move down.
• From a cell $(r, c)$, the ladybug can move right to $(r, c+1)$. If $c = C$ (the move from column $C$ to column $C+1$), the ladybug has escaped the maze and the experiment ends.
• In short, apart from escaping from the last column, the ladybug can move freely up, down, and right, but it cannot move left.

The figure below shows the case $R = 3$, $C = 2$, $N = 2$, $x = [3, 3]$, $y = [1, 2]$, and $I = 1$. The two cells marked "x" contain obstacles, and the ladybug starts at $(I, 1) = (1, 1)$. When the ladybug escapes by moving right from column $C$, it reaches one of the cells marked "#" in the figure. For convenience, let $F_c$ be the row number of the first cell the ladybug visits in column $c$. It always holds that $F_1 = I$.

The figure below shows three escape routes that reach cell $(1, 3)$. For convenience, the four cells the ladybug passes through other than the endpoints are labeled A, B, C, and D.

• Route 1: A -> B -> D -> C -> escape. Here $F = [1, 2, 1]$.
• Route 2: A -> B -> A -> B -> D -> C -> D -> C -> escape. Here $F = [1, 2, 1]$.
• Route 3: A -> B -> A -> B -> A -> C -> D -> C -> escape. Here $F = [1, 1, 1]$.

Albert's apparatus can record which cells the ladybug visited and the first cell it visited in each column. It cannot record how many times a cell was visited or the order of the visits. So Routes 1 and 2 cannot be told apart, since both visit cells A, B, C, and D and have the same $F$. Route 3 can be told apart from them, because it has the same visited cells but a different $F_2$.

In the maze above, the ladybug can escape in 9 ways that the apparatus can tell apart, shown in the figure below. In the figure, "x" marks an obstacle and "*" marks the first cell visited in that column. For each escape, let $S$ be the set of visited cells.

• Top row, left to right:
  • $S = \{ (1, 1), (1, 2), (1, 3) \}$, $F = [1, 1, 1]$. For example, (1, 1) -> (1, 2) -> (1, 3).
  • $S = \{ (1, 1), (1, 2), (2, 2), (1, 3) \}$, $F = [1, 1, 1]$. For example, (1, 1) -> (1, 2) -> (2, 2) -> (1, 2) -> (1, 3).
  • $S = \{ (1, 1), (2, 1), (1, 2), (1, 3) \}$, $F = [1, 1, 1]$. For example, (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]$. For example, (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]$. For example, (1, 1) -> (2, 1) -> (2, 2) -> (1, 2) -> (1, 3).
• Bottom row, left to right:
  • $S = \{ (1, 1), (1, 2), (2, 2), (2, 3) \}$, $F = [1, 1, 2]$. For example, (1, 1) -> (1, 2) -> (2, 2) -> (2, 3).
  • $S = \{ (1, 1), (2, 1), (2, 2), (2, 3) \}$, $F = [1, 2, 2]$. For example, (1, 1) -> (2, 1) -> (2, 2) -> (2, 3).
  • $S = \{ (1, 1), (2, 1), (1, 2), (2, 2), (2, 3) \}$, $F = [1, 1, 2]$. For example, (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]$. For example, (1, 1) -> (2, 1) -> (2, 2) -> (1, 2) -> (2, 2) -> (2, 3).

These 9 are the only distinguishable ways for the ladybug to escape this maze.

Two escape routes are the same method if they visit the same set of cells $S$ and have the same first-visit values $F$. Albert wants the number of distinguishable escapes that reach cell $(r, C+1)$, denoted $A_r$, because the exit cell matters. For the maze above, $A = [5, 4, 0]$.

Given $R$, $C$, $N$, $I$, and the arrays $x$ and $y$, compute $A_1, A_2, \dots, A_R$.

The first line contains the number of test cases $T$.

The first line of each test case contains $R$, $C$, $N$, and $I$, separated by spaces. Each of the next $N$ lines contains two integers separated by a space. The two integers on the $i$-th line are the position $x_i, y_i$ of the $i$-th obstacle.

For each test case, print the answers $A_1, A_2, \dots, A_R$ on one line, separated by spaces. The values can be very large, so print each one modulo $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$
• For every $i$ with $1 \le i \le N$:
  • $1 \le x_i \le R$
  • $1 \le y_i \le C$
  • $(x_i, y_i) \neq (I, 1)$ (no obstacle is placed on the starting cell)
  • $(x_i, y_i)$ is unique