公司计划在一个拥有 $N$ 条横向街道和 $M$ 条纵向街道的城市中开设办公室，每个交叉路口都有一栋建筑。每栋建筑都通过最多两条纵向道路和两条横向道路与其邻居相连，每条道路的长度均为 1。
在夜间，只有 $N \times M - 1$ 条道路是照明的，其余道路不可用。这些照明的道路恰好构成一棵树，即它们足以连接任意两栋建筑。
第一张图展示了夜间的道路情况，第二张图展示了白天的道路情况。第三张图是一个简单的示例，将在下文解释中使用。
每栋建筑都可以被购买并改建为办公室。每个月，你都需要巡视这些办公室，从一栋建筑出发，访问所有已改建的办公建筑，最后回到起始建筑。你将利用可用的道路完成此任务，并使巡视的总长度最小化，尽管你无法确定具体的巡视时间（白天或夜间）。
在右侧的示例中，如果选择在建筑 $A, D$ 和 $F$ 开设办公室，则白天的巡视长度为 6，夜间的巡视长度为 10。
为了避免规划上的复杂性，公司决定以一种确保巡视最小长度在白天和夜间保持一致的方式来选择办公建筑。
你需要计算满足给定要求的办公建筑选择方案数。如果两种选择中至少有一栋建筑不同，则视为不同的选择。由于方案数可能很大，请输出其对 $1\,000\,000\,007$ 取模的结果。
请注意，办公室的数量有限制。详情请参阅输入格式。
输入格式
第一行包含三个整数：$N, M$ 和 $T$。$T$ 表示你计划开设的办公室的准确数量，但当 $T = 1$ 时，你可以开设任意数量的办公室，但至少需要开设两间。
接下来的 $N$ 行，每行包含 $M$ 个字符（无空格）。第 $i+1$ 行的第 $j$ 个字符为 '0', '1', '2' 或 '3'，描述了从位于从上往下第 $i$ 条街道、从左往右第 $j$ 条街道的建筑出发，在夜间照明的道路情况：
- '0' 表示该建筑没有通往上方或左侧的道路。
- '1' 表示该建筑有一条通往其正上方建筑的道路。
- '2' 表示该建筑有一条通往其左侧建筑的道路。
- '3' 表示该建筑有通往其正上方和左侧建筑的道路。
共有 $N \times M - 1$ 条道路，且它们构成一棵树。
输出格式
输出一个整数：方案数对 $10^9 + 7$ 取模的结果。
样例
样例 1
2 3 2 022 031
12
对应上述图片。 办公室可以在以下建筑对中开设：{A, B}, {A, C}, {A, E}, {A, F}, {B, C}, {B, D}, {B, E}, {B, F}, {C, D}, {C, E}, {C, F}, {D, E}。
样例 2
2 3 3 022 031
10
同一城市，当 $T = 3$ 时。办公室可以在以下建筑三元组中开设：{A, B, C}, {A, B, E}, {A, B, F}, {A, C, E}, {A, C, F}, {B, C, D}, {B, C, E}, {B, C, F}, {B, D, E}, {C, D, E}。
样例 3
2 3 1 022 031
25
除了上述 $T = 2$ 和 $T = 3$ 的可能性外，办公室还可以通过以下方式开设：{A, B, C, E}, {A, B, C, F}, {B, C, D, E}。
数据范围
- $1 \le T \le 3$
- $1 \le N, M \le 1\,000$
子任务
- (4 分) $M, N \le 2$
- (5 分) $N = 1$
- (9 分) $T = 2; N, M \le 50$
- (11 分) $T = 2$
- (9 分) $T = 3; N, M \le 20$
- (13 分) $T = 3$
- (14 分) $T = 1; M, N \le 4$
- (10 分) $T = 1; N, M \le 50$
- (9 分) $T = 1$; 道路描述中不包含字符 '3'。
- (16 分) $T = 1$
Figure 1. 第一张图展示了夜间的道路情况，第二张图展示了白天的道路情况。第三张图是一个简单的示例，将在下文解释中使用。