拼图（puzzle）

题目背景

奶龙神喜欢玩大小为 $10^9\times10^9$ 的拼图。

题目描述

奶龙神有一种拼图，如下图所示：

奶龙神可以将这块拼图任意旋转，得到了四种方向的拼图，并对这四种方向分别标号为 $1,2,3,4$，如下图所示：

奶龙神想要拼出一幅 $n\times m$ 的拼图。奶龙神认为一种方案是“美妙的”，当且仅当拼图符合以下条件：

• 对于任意的相邻两块拼图，相连的那条边的中点，在两块拼图上相连的两条曲线颜色必须相同；
• 同一种颜色的曲线不形成闭合的曲线。

例如，下图中的三种方案，只有第一种是“美妙的”。第二种和第三种分别违反了第一条约束和第二条约束。

奶龙神想要固定拼图中一些位置的拼图方向，并且希望知道有多少种放置剩余位置的拼图，使得这种方案是“美妙的”。并且奶龙神会不断调整这些固定的位置。具体地，初始 $n\times m$ 的拼图是空的，接下来给定 $q$ 次操作，每次操作形如下面两种之一：

• 固定第 $x$ 行第 $y$ 列的拼图方向为 $t$，保证此时不存在这个位置上的方向约束；
• 删除第 $x$ 行第 $y$ 列的拼图方向的约束，保证此时存在这个位置上的方向约束。

你的任务是在全部 $q$ 次操作开始前，以及每次操作之后，计算放置剩余位置的拼图使得整幅拼图是“美妙的”的方案数。由于答案可能很大，所以你只需要输出答案对 $10^4+7=10007$ 取模的结果。

注意：没有答对所有 $q+1$ 个答案也有可能获得部分分数。具体请看“评分方式”部分。

输入格式

输入的第一行包含三个正整数 $n,m,q$。

接下来 $q$ 行，每行先输入一个字符 $o$：

• 若 $o$ 为 +，那么接下来输入三个整数 $x,y,t$，表示固定第 $x$ 行第 $y$ 列的拼图方向为 $t$；
• 若 $o$ 为 -，那么接下来输入两个整数 $x,y$，表示删除第 $x$ 行第 $y$ 列的拼图方向的约束。

输出格式

输出包含 $q+1$ 行，每行包含一个整数，依次表示全部 $q$ 次操作开始前，以及每次操作之后的答案。

样例 1 输入

2 2 3
+ 1 1 1
+ 2 2 3
- 1 1

样例 1 输出

14
3
0
3

样例 1 解释

初始状态下，整幅拼图没有任何约束，并且方案数为 $14$。

接下来在第 $1$ 行第 $1$ 列添加一个约束，方案数变为 $3$。

接下来在第 $2$ 行第 $2$ 列添加一个约束，此时整幅拼图的约束状态形如下图：

此时可以证明不存在“美妙的”方案，答案为 $0$。

接下来删除第 $1$ 行第 $1$ 列的约束后，方案数又变为 $3$。

      |

评分方式

对于单个测试点，选手获得的分数按照如下方式计算：

• 若选手正确回答了所有 $q+1$ 个答案，那么该测试点得满分；
• 否则，若选手输出文件的第一行与答案文件的第一行一致，那么该测试点得到 $50\%$ 的分数；
• 否则，该测试点不得到任何分数。

数据范围

对于所有测试数据保证：

• $1\le n,m\le10^9$；
• $1\le q\le2\times10^5$；
• $1\le x\le n$，$1\le y\le m$，$1\le t\le4$。

本题采用捆绑测试。 单个子任务中选手的得分等于该子任务中所有测试点得分的最小值。

特殊性质：保证 $n=1$。