Strange Calculation and Cats

题意翻译

## 题目翻译 LBW 有一张 $n\times m$ 的网格图，有一只猴子初始在$(1,1)$。 猴子每秒钟可以移动一格，或者不动。 LBW 有 $T$ 次操作，每一次询问想知道不同的内容，如下。 + 操作一：询问第 $i$ 秒时，猴子走到 $(x, y)$ 的方案数。 + 操作二：第 $i$ 秒，$(x, y)$ 出现了障碍，不能走在障碍上。 + 操作三：第 $i$ 秒，$(x, y)$ 出的障碍消失了。 对于所有操作一，告诉 LBW 方案数。 ## 输入格式 第一行三个整数 $T$，$n$，$m$，分别表示操作数量，地图的行数与列数。 接下来 $T$ 行，每行四个数 $op, x, y, i$，如题目所述。$op$ 表示操作类型。 ## 输出格式 对于所有操作一，单独一行给出方案数。这个答案可能很大，只需给出它 $\bmod\space 10^9 + 7$ 的结果。 ## 数据范围 $n \times m \le 20$ $1 \le T \le 10^4$ 每次操作，保证 $op \in \{1, 2, 3\}$，$1 \le x \le n$ 并且 $1 \le y \le m$，$i \le 10^9$。 保证每个格子最多只有一个障碍，且 $i$ 是递增的。

题目描述

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 $ 10^{9}+7 $ .

输入输出格式

输入格式

The first line of the input contains three positive integers $ n $ , $ m $ and $ q $ ( $ 1<=n·m<=20,1<=q<=10000 $ ) — 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<=10^{9} $ ) — 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}&lt;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.

输入输出样例

输入样例 #1

1 3 3
2 1 2 3
3 1 2 5
1 1 1 7

输出样例 #1

5

输入样例 #2

3 3 3
2 2 2 2
1 3 3 5
1 3 3 7

输出样例 #2

2
42

输入样例 #3

4 5 5
2 2 5 3
2 2 4 6
3 2 4 9
1 4 4 13
1 4 4 15

输出样例 #3

490902
10598759

说明

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.