题目描述

高橋君はお母さんからグリッドをもらいました。このグリッドは縦 $H$ マス×横 $W$ マスからなり、各マスは黒か白で塗られています。 黒いマス全体は、縦横にひとつながりになっています。

このグリッドの $i$ 行 $j$ 列 $(1\ ≦\ i\ ≦\ H,\ 1\ ≦\ j\ ≦\ W)$ のマスの情報は、縦横に並んだ文字 $s_{ij}$ であらわされ、 $s_{ij}$ が # のときこのマスが黒く、 . のとき白く塗られていることを表します。少なくともひとつのマスが黒く塗られています。

レベル $0$ のフラクタルとは黒いマスひとつからなる $1\ ×\ 1$ のグリッドであり、 レベル $k+1$ のフラクタルとは、レベル $k$ のフラクタルを、お母さんからもらったグリッドの全ての黒いマスに相当する位置に並べ、白いマスに相当する位置は白いマスで埋めたものを指します。

お母さんからもらったグリッドの情報と整数 $K$ が与えられるので、レベル $K$ のフラクタルに黒いマスからなる連結成分がいくつあるかを $10^9+7$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $K$ $s_{11}\ ..\ s_{1W}$ : $s_{H1}\ ..\ s_{HW}$

输出格式

レベル $K$ のフラクタルにある黒いマスからなる連結成分の個数を $10^9+7$ で割ったあまりを一行に出力せよ。

题目大意

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

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

我们定义「$n$ 级分形」如下：$0$ 级分形是一个 $1\times1$ 的黑色单元格。$n$ 级分形由 $n-1$ 级分形变化而来。具体地，将 $n-1$ 级分形的每一个黑色单元格替换为 Snuke 的网格，每一个白色单元格替换为与 Snuke 的网格尺寸相同的全部为白色的网格，就成了 $n$ 级分形。

Snuke 喜欢连通块。现在他想你告诉他，$K$ 级分形中，有多少个黑色格子组成的四联通块？

为了避免输出量超出不着实际的边界，Snuke 要你对 $10^9+7$ 取模。

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

20

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

1

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

301811921

提示

制約

• $1\ ≦\ H,W\ ≦\ 1000$
• $0\ ≦\ K\ ≦\ 10^{18}$
• $s_{ij}$ は # か . のいずれかである。
• # のマス全体は縦横に連結である。
• # のマスは少なくともひとつ存在する。

Sample Explanation 1

この入力例で作られるフラクタルは、以下のようなものです。この黒マスからなる連結成分の数は $20$ なので、$20$ を出力します。 .............#............. ............###............ ............#.#............ ..........#..#..#.......... .........#########......... .........#.##.##.#......... ..........#.....#.......... .........###...###......... .........#.#...#.#......... ....#........#........#.... ...###......###......###... ...#.#......#.#......#.#... .#..#..#..#..#..#..#..#..#. ########################### #.##.##.##.##.##.##.##.##.# .#.....#..#.....#..#.....#. ###...######...######...### #.#...#.##.#...#.##.#...#.# ....#.................#.... ...###...............###... ...#.#...............#.#... .#..#..#...........#..#..#. #########.........######### #.##.##.#.........#.##.##.# .#.....#...........#.....#. ###...###.........###...### #.#...#.#.........#.#...#.#