题目描述

本题译自 eJOI2023 Problem C. Opening Offices

你的公司计划在一个有 $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$ 个字符描述了夜间从位于顶部第 $i$ 条街和左侧第 $j$ 条街的建筑出发的照明道路：

• 0 表示这栋建筑没有通往其上方或左侧方向的道路。
• 1 表示这栋建筑有一条通往其正上方的建筑的道路。
• 2 表示这栋建筑有一条通往其左侧的建筑的道路。
• 3 表示这栋建筑有通往其正上方和左侧的建筑的道路。

共有 $N \times M - 1$ 条道路，它们形成了一棵树。

输出格式

输出一个整数，表示方案数模 $10^9 + 7$。

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 3 3
022
031

10

与样例 1 相同的城市，$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}。

2 3 1
022
031

25

除了上面显示的 $T = 2$ 和 $T = 3$ 的可能性之外，办公室还可以以下方式开设：{A, B, C, E}，{A, B, C, F}，{B, C, D, E}。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq T \leq 3$
• $1 \leq N , M \leq 1000$

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$M , N \leq 2$	$4$
$2$	$N = 1$	$5$
$3$	$T = 2; N , M \leq 50$	$9$
$4$	$T = 2$	$11$
$5$	$T = 3;N , M \leq 20$	$9$
$6$	$T = 3$	$13$
$7$	$T = 1; M , N \leq 4$	$14$
$8$	$T = 1; N , M \leq 50$	$10$
$9$	$T = 1$；不存在 3 的道路	$9$
$10$	$T = 1$	$16$