Background

Little L is a frog, and he is now preparing to travel in City A.

Problem Description

City A is an $n\times m$ matrix. There is a given number $k$. There is also a variable $w$, initially $0$. Let $(r,c)$ denote the cell in row $r$ and column $c$.

In this matrix, there are $t$ special points. The $i$-th one is at $(x_i,y_i)$ with type $p_i$ ($p_i\in\{1,2\}$). If $p_i=2$, it has an additional attribute $s_i$. It is guaranteed that there do not exist $i,j$ such that $i\neq j$ and $x_i=x_j,y_i=y_j$.

Little L starts at $(1,1)$. He can perform any number of one of the following jump operations until he reaches $(n,m)$. Suppose he is currently at $(a,b)$:

• Choose an $h$ such that $0\le h\le k$, and there does not exist $1\le i\le h$ such that $(a+i,b)$ is a type $2$ special point. Then jump to $(a+h+1,b)$.
• Choose an $h$ such that $0\le h\le k$, and there does not exist $1\le i\le h$ such that $(a,b+i)$ is a type $2$ special point. Then jump to $(a,b+h+1)$.
• Choose an $h$ such that $0\le h\le k$, and there does not exist $1\le i\le h$ such that $(a+i,b+i)$ is a type $2$ special point. Then jump to $(a+h+1,b+h+1)$.

After each jump, suppose it lands at $(X,Y)$. If $(X,Y)$ is the $Z$-th special point, then:

• If $p_Z=1$, then $w\leftarrow w+1$.
• If $p_Z=2$, let $w\leftarrow w-s_Z$.

If in some plan, at any moment $w<0$, or at any moment $(X,Y)$ is not inside the matrix, then this plan is invalid.

Ask for the number of valid plans to reach $(n,m)$, modulo $10^9+7$. Two plans are different if and only if the sequences of $(X,Y)$ visited each time are different.

Input Format

The first line contains $4$ integers $n,m,k,t$.

The next $t$ lines each start with an integer $p_i$, then:

• If $p_i=1$, input $2$ integers $x_i,y_i$, representing a type $1$ special point.
• If $p_i=2$, input $3$ integers $x_i,y_i,s_i$, representing a type $2$ special point.

Output Format

Output one integer on the first line, the answer.

3 3 1 2
1 1 3
2 2 3 1

15

3 3 1 0

22

Hint

[Sample Explanation #1]

Note: Each point below represents a cell. A red arrow is one jump, and the tail of the arrow is $(X,Y)$. Yellow points are special points with $p_i=1$. Green points are special points with $p_i=2$.

The following $15$ plans are valid:

The following $5$ plans are invalid, because in these plans, after Little L reaches $(2,3)$, $w=-1<0$:

The following $2$ plans are invalid, because in these plans, Little L jumps over a special point with $p_i=2$:

[Sample Explanation #2]

Since there are no special points, in sample explanation #1, the $15$ valid plans shown and the $7$ invalid plans are all valid in sample #2, so the answer is $22$.

[Constraints]

This problem uses bundled testdata.

• Subtask #1 ($15\text{ pts}$): $n,m\le8$.
• Subtask #2 ($25\text{ pts}$): $k=0$.
• Subtask #3 ($25\text{ pts}$): $t=0$.
• Subtask #4 ($35\text{ pts}$): no additional constraints.

For $100\%$ of the data, $1\le x_i\le n\le180$, $1\le y_i\le m\le180$, $0\le k\le \max\{n,m\}+1$, $0\le t\le n\times m-2$, $p_i\in\{1,2\}$, $1\le s_i\le356$.

It is guaranteed that no two pairs $(x_i,y_i)$ are the same, and it is guaranteed that $(x_i,y_i)\neq(1,1)$ and $(x_i,y_i)\neq(n,m)$.

Translated by ChatGPT 5