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.