题目描述

声明：本题为原题转载及翻译，若侵犯了您的合法权益，请与本站联系，我们将删除题目。

原题链接

Snuke 从他的母亲那里得到了生日礼物——一个网格。网格有 $H$ 行 $W$ 列。每个单元格都是黑色或白色。所有黑色单元格都是四联通的，也就是说，只做水平或垂直移动且只经过黑色单元格即可从任何黑色单元格移动到任何其他黑色单元格。

第 $i$ 行第 $j$ 列（$1\le i\le H,1\le j\le W$）的单元格的颜色由字符 $s_{ij}$ 表示。如果 $s_{ij}$ 是 #，该单元格为黑色；如果 $s_{ij}$ 是 .，该单元格为白色。至少一个单元格是黑色的。

我们定义「分形」如下：$0$ 级分形是一个 $1\times 1$ 的黑色单元格。$k+1$ 级分形由 $H$ 行 $W$ 列较小一级的分形按照 Snuke 的网格的样式拼成：与 Snuke 网格中的黑色单元格对应的位置是一个 $k$ 级分形；与 Snuke 网格中的白色单元格对应的位置是一个单元格全部为白色，尺寸与 $k$ 级分形相同的网格。

您将得到 Snuke 的网格的描述和整数 $K$。请求出 $K$ 级分形中黑色单元格组成的连通分量数，模 $10^9+7$。

输入格式

输入从标准输入流按以下形式给出：

$H$　$W$　$K$
$s_{11}\cdots s_{1W}$
$\vdots$
$s_{H1}\cdots s_{HW}$

输出格式

输出 $K$ 级分形中黑色单元格组成的连通分量数，模 $10^9+7$。

3 3 3
.#.
###
#.#

20

3 3 3
###
#.#
###

1

11 15 1000000000000000000
.....#.........
....###........
....####.......
...######......
...#######.....
..##.###.##....
..##########...
.###.....####..
.####...######.
###############
#.##..##..##..#

301811921

数据范围与提示

对于所有数据：

• $1\le H,W\le 1000$
• $0\le K\le 10^{18}$
• 每个 $s_{ij}$ 是 # 或 .
• 网格中所有黑色单元格四联通
• 网格中至少有一个黑色单元格