← 返回题目列表

Codeforces · 593/E

E. 奇怪的计算和猫

中文机器翻译题面 查看原题

Gosha 的宇宙是一个由 n 行和 m 列组成的表。行和列都用从 1 开始的连续整数进行编号。我们将使用 (r, c) 来表示位于 r 行和 c 列的单元格。

Gosha 经常被邀请到某个地方。每次他收到邀请时,他都会先计算出到达这个地方的路数,然后才去。 Gosha 的房子位于牢房 (1, 1) 内。

在任何时刻,Gosha 都会从他当前所在的单元格移动到与其相邻的单元格(如果两个单元格共享公共边,则它们是相邻的)。当然,只有存在这样的单元格,移动才是可能的,即Gosha不会超出表格的边界。因此,他能够从单元格 (r, c) 移动到单元格 (r - 1, c)、(r, c - 1)、(r + 1, c)、(r, c + 1) 之一。此外,Ghosha 可以跳过一步并留在当前单元格 (r, c)。

除了喜欢奇怪的计算之外,Gosha 对猫过敏,所以他从不去有猫的牢房。 Gosha 确切地知道他将在何时何地受到邀请,以及猫沿着桌子走动的时间表。形式上,他有 q 条记录,其中第 i 条具有以下形式之一:

- 1, xi, yi, ti - Gosha 被邀请在时间 ti 来到单元格 (xi, yi)。保证此时单元格(xi, yi)内没有猫。
- 2, xi, yi, ti - 在 ti 时刻,单元格 (xi, yi) 中出现了一只猫。保证此时没有其他猫位于该单元格 (xi, yi) 中。
- 3, xi, yi, ti - 在 ti 时刻,一只猫离开了单元格 (xi, yi)。保证单元格 (xi, yi) 中有一只 cat。

Gosha 计划只接受一份邀请,但他尚未决定是哪一份邀请。为了做出这个决定,他要求您计算每个邀请 i 在时刻 ti 到达单元格 (xi, yi) 的方式数。对于每个邀请,假设 Gosha 在时刻 1 开始从单元格 (1, 1) 移动。

在两个相邻单元之间移动 Gosha 正好需要一个 tim 单位。特别是,这意味着只有当 Gosha 开始从相邻牢房移动时,坐在牢房中的猫离开牢房,并且当 Gosha 在牢房中时没有猫进入牢房,Gosha 才能进入该牢房。

如果在从 1 到 t 的至少一个时刻,Gosha 的位置在此时的两条路线上是不同的,则在时间 t 时从单元格 (1, 1) 到单元格 (x, y) 的两条路线被认为是不同的。请注意,在此旅行期间,Gosha 可以多次访问 (1, 1) 和 (x, y)。由于路数可能相当大,因此将其打印为 109 + 7 模。

输入

输入的第一行包含三个正整数 n、m 和 q (1 ≤ n·m ≤ 20, 1 ≤ q ≤ 10 000) — 分别是表中的行数和列数以及事件数。

接下来 q 行描述事件,每个描述包含四个整数 tpi、xi、yi 和 ti (1 ≤ tp ≤ 3, 1 ≤ x ≤ n, 1 ≤ y ≤ m, 2 ≤ t ≤ 109) - 事件类型(如果 Gosha 收到邀请则为 1,如果猫来到牢房则为 2,如果猫离开牢房则为 3)、坐标分别是发生动作的单元格和动作发生的时刻。

保证查询按时间顺序给出,即 ti < ti + 1。

输出

对于每个邀请 i(即 tpi = 1),计算在时间 ti 时刻到达单元格 (xi, yi) 的方式数。按时间顺序(即按照它们在输入中出现的顺序)回复邀请。

示例

输入 #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

注意

第一个示例的说明。每张图片都指定了在适当的时间到达单元格的方式数量。 (X代表在这个特定时刻被阻塞的单元格)

时刻 1. 时刻 2. 时刻 3. 时刻 4. 时刻 5. 时刻 6. 时刻 7.