CF593E.Strange Calculation and Cats

Gosha's universe is a table consisting of n rows and m columns. Both the rows and columns are numbered with consecutive integers starting with 1. We will use (r, c) to denote a cell located in the row r and column c.

Gosha is often invited somewhere. Every time he gets an invitation, he first calculates the number of ways to get to this place, and only then he goes. Gosha's house is located in the cell (1, 1).

At any moment of time, Gosha moves from the cell he is currently located in to a cell adjacent to it (two cells are adjacent if they share a common side). Of course, the movement is possible only if such a cell exists, i.e. Gosha will not go beyond the boundaries of the table. Thus, from the cell (r, c) he is able to make a move to one of the cells (r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1). Also, Ghosha can skip a move and stay in the current cell (r, c).

Besides the love of strange calculations, Gosha is allergic to cats, so he never goes to the cell that has a cat in it. Gosha knows exactly where and when he will be invited and the schedule of cats travelling along the table. Formally, he has q records, the i-th of them has one of the following forms:

• 1, x__i, y__i, t__i — Gosha is invited to come to cell (x__i, y__i) at the moment of time t__i. It is guaranteed that there is no cat inside cell (x__i, y__i) at this moment of time.
• 2, x__i, y__i, t__i — at the moment t__i a cat appears in cell (x__i, y__i). It is guaranteed that no other cat is located in this cell (x__i, y__i) at that moment of time.
• 3, x__i, y__i, t__i — at the moment t__i a cat leaves cell (x__i, y__i). It is guaranteed that there is cat located in the cell (x__i, y__i).

Gosha plans to accept only one invitation, but he has not yet decided, which particular one. In order to make this decision, he asks you to calculate for each of the invitations i the number of ways to get to the cell (x__i, y__i) at the moment t__i. For every invitation, assume that Gosha he starts moving from cell (1, 1) at the moment 1.

Moving between two neighboring cells takes Gosha exactly one unit of tim. In particular, this means that Gosha can come into the cell only if a cat sitting in it leaves the moment when Gosha begins his movement from the neighboring cell, and if none of the cats comes to the cell at the time when Gosha is in it.

Two ways to go from cell (1, 1) to cell (x, y) at time t are considered distinct if for at least one moment of time from 1 to t Gosha's positions are distinct for the two ways at this moment. Note, that during this travel Gosha is allowed to visit both (1, 1) and (x, y) multiple times. Since the number of ways can be quite large, print it modulo 109 + 7.

戈沙的宇宙是一个由 $n$ 行 $m$ 列组成的表格。行与列均用从 $1$ 开始的连续整数编号。我们用 $(r,\,c)$ 表示位于第 $r$ 行、第 $c$ 列的格子。

戈沙经常收到外出邀请。每次收到邀请时，他总是先计算到达该地点的方法数，然后才出发。戈沙的家位于格子 $(1,\,1)$。

在任意时刻，戈沙只能从当前所在格子移动到与其相邻的格子（两个格子相邻当且仅当它们有一条公共边）。当然，这种移动仅在目标格子存在时才可行，即戈沙不会移出表格边界。因此，从格子 $(r,\,c)$ 出发，他可移动至以下格子之一：$(r-1,\,c)$、$(r,\,c-1)$、$(r+1,\,c)$、$(r,\,c+1)$。此外，戈沙也可选择跳过移动，停留在当前格子 $(r,\,c)$。

除了热衷于奇特的计算外，戈沙对猫严重过敏，因此他绝不会进入有猫的格子。戈沙确切地知道他将在何时收到哪些邀请，以及猫在表格中移动的时间表。形式化地说，他共有 $q$ 条记录，其中第 $i$ 条为如下三种类型之一：

• 1 $x_i$ $y_i$ $t_i$ —— 戈沙被邀请于时刻 $t_i$ 到达格子 $(x_i,\,y_i)$。保证在此时刻格子 $(x_i,\,y_i)$ 内没有猫。
• 2 $x_i$ $y_i$ $t_i$ —— 在时刻 $t_i$，一只猫出现在格子 $(x_i,\,y_i)$ 中。保证在此时刻格子 $(x_i,\,y_i)$ 内没有其他猫。
• 3 $x_i$ $y_i$ $t_i$ —— 在时刻 $t_i$，一只猫离开格子 $(x_i,\,y_i)$。保证在此时刻格子 $(x_i,\,y_i)$ 内确有一只猫。

戈沙计划只接受其中一项邀请，但尚未决定具体接受哪一项。为了辅助决策，他请你为每项邀请 $i$ 计算：在时刻 $t_i$ 到达格子 $(x_i,\,y_i)$ 的方法数。对每一项邀请，均假设戈沙于时刻 $1$ 从格子 $(1,\,1)$ 出发。

戈沙在两个相邻格子之间移动恰好耗时 $1$ 单位时间。特别地，这意味着：戈沙仅可在一只猫恰好于他从相邻格子出发的同一时刻离开目标格子时进入该格子；且在他处于某格子的时刻，不能有任何猫进入该格子。

若存在某个时刻 $\tau \in [1,\,t]$，使得两条从 $(1,\,1)$ 到 $(x,\,y)$、耗时 $t$ 的路径在该时刻 $\tau$ 所处位置不同，则认为这两条路径是不同的。注意，在整个行程中，戈沙可以多次访问起点 $(1,\,1)$ 和终点 $(x,\,y)$。由于方法数可能非常大，请将结果对 $10^9 + 7$ 取模后输出。

The first line of the input contains three positive integers n, m and q (1 ≤ n·m ≤ 20, 1 ≤ q ≤ 10 000) — the number of rows and columns in the table and the number of events respectively.

Next q lines describe the events, each description contains four integers tp__i, x__i, y__i and t__i (1 ≤ tp ≤ 3, 1 ≤ x ≤ n, 1 ≤ y ≤ m, 2 ≤ t ≤ 109) — the type of the event (1 if Gosha gets an invitation, 2 if a cat comes to the cell and 3 if a cat leaves the cell), the coordinates of the cell where the action takes place and the moment of time at which the action takes place respectively.

It is guaranteed that the queries are given in the chronological order, i.e. t__i < t__i + 1.

输入的第一行包含三个正整数 $n$、$m$ 和 $q$（$1 ≤ n·m ≤ 20$，$1 ≤ q ≤ 10\,000$），分别表示表格的行数、列数以及事件总数。

接下来的 $q$ 行描述了各个事件，每行包含四个整数 $tp_i$、$x_i$、$y_i$ 和 $t_i$（其中 $1 ≤ tp ≤ 3$，$1 ≤ x ≤ n$，$1 ≤ y ≤ m$，$2 ≤ t ≤ 10^9$）：分别表示事件类型（1 表示 Gosha 收到邀请，2 表示一只猫进入该格子，3 表示一只猫离开该格子）、事件发生的格子坐标 $(x, y)$，以及事件发生的时间 $t$。

保证所有查询按时间顺序给出，即 $t_i < t_{i+1}$。

For each invitation i (that is, tp__i = 1) calculate the number of ways to get to cell (x__i, y__i) at the moment of time t__i. Respond to the invitations chronologically, that is, in the order they appear in the input.

对于每个邀请 i（即 tp__i = 1），计算在时刻 t__i 到达格子 (x__i, y__i) 的方案数。按时间顺序响应这些邀请，即按照它们在输入中出现的顺序输出答案。

Explanation of the first sample. Each picture specifies the number of ways to arrive at the cell at the appropriate time. (X stands for a cell blocked at this particular moment of time)

Time moment 1.

Time moment 2.

Time moment 3.

Time moment 4.

Time moment 5.

Time moment 6.

Time moment 7.

第一个样例的说明。每张图表示在对应时刻到达该格子的方案数。（X 表示该时刻被封锁的格子）

时刻 1。

时刻 2。

时刻 3。

时刻 4。

时刻 5。

时刻 6。

时刻 7。