仲裁法院的任务是将一片由两个邻国——国家 A 和国家 B 共同声索主权的湾区进行划分。该湾区可以用一个矩形网格表示，网格由 $n$ 行和 $m$ 列组成，行从上到下依次编号为 $1$ 到 $n$，列从左到右依次编号为 $1$ 到 $m$。法院里有 $n - 1$ 名所谓的水平裁判和 $m - 1$ 名所谓的垂直裁判在辛勤工作。每位水平裁判负责相邻两行之间的一条水平线。类似地，每位垂直裁判负责相邻两列之间的一条垂直线。
图 1：与下方第一个样例中期望划分一致的一种有效投票组合。
每位裁判的工作结果是其投出的一票——一个介于 $1$ 和 $k$ 之间（含边界）的正整数。每个格子的值是一个整数，其计算方法是：将负责该格子上方 and 左侧线条的所有裁判的投票数相加，然后减去负责其他线条（即该格子下方和右侧线条）的所有裁判的投票数。投票结束后，湾区将按如下方式划分：值负的格子归属于国家 A，值正的格子归属于国家 B。如果某个格子的值为零，则投票结果无效。
现在给定了一个期望的划分结果。具体来说，对于每个格子，已知它必须归属于哪个国家。设 $c$ 为使得投票有效且产生给定划分结果的不同投票组合数，求 $c \bmod (10^9 + 7)$ 的值。
输入格式
第一行包含三个正整数 $n$、$m$ 和 $k$ —— 湾区的行数、列数以及最大可能的投票数。
接下来的 $n$ 行中，每行包含一个长度为 $m$ 的字符串，描述湾区的一行。需要归属于国家 A 的格子用 - 表示，需要归属于国家 B 的格子用 + 表示。
输出格式
输出满足要求的投票组合数模 $10^9 + 7$ 的结果。
数据范围
在所有子任务中，满足 $1 \le n, m, k \le 80$。
| 子任务 | 分值 | 限制条件 |
|---|---|---|
| 1 | 10 | $n + m \le 10$, $k \le 4$ |
| 2 | 10 | $m = 1$ |
| 3 | 10 | $n, m, k \le 20$ |
| 4 | 20 | $n, m, k \le 40$ |
| 5 | 20 | $m = n + 1$，第 $r$ 行第 $s$ 列的格子被标记为 + 当且仅当 $r + s \ge 1 + m$ |
| 6 | 30 | 无附加限制 |
样例
输入格式 1
4 6 4 -----+ ----++ --++++ -+++++
输出格式 1
2364
输入格式 2
3 3 2 --+ --+ -++
输出格式 2
2
输入格式 3
2 3 2 --- +++
输出格式 3
0