题目描述

高桥君从妈妈那里得到了一张网格。这张网格由 $H$ 行 $W$ 列的格子组成，每个格子被涂成黑色或白色。所有黑色格子在纵横方向上是连通的。

第 $i$ 行第 $j$ 列 $(1 \leq i \leq H,\ 1 \leq j \leq W)$ 的格子的信息由字符 $s_{ij}$ 表示，$s_{ij}$ 为 # 时表示该格子为黑色，为 . 时表示该格子为白色。至少有一个格子是黑色。

“等级 $0$ 的分形”是指仅包含一个黑色格子的 $1 \times 1$ 网格。“等级 $k+1$ 的分形”是指，将等级 $k$ 的分形分别放置在妈妈给的网格中所有黑色格子对应的位置上，白色格子对应的位置用白色格子填充而成。

给定妈妈给的网格信息和整数 $K$，请你求出等级 $K$ 的分形中由黑色格子组成的连通分量的个数，并对 $10^9+7$ 取模输出。

输入格式

输入以以下格式从标准输入读入。

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

输出格式

输出等级 $K$ 的分形中黑色格子组成的连通分量的个数，对 $10^9+7$ 取模。

样例 1

输入

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

输出

20

样例 2

输入

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

输出

1

样例 3

输入

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

输出

301811921

说明/提示

限制条件

• $1 \leq H, W \leq 1000$
• $0 \leq K \leq 10^{18}$
• $s_{ij}$ 只可能是 # 或 .。
• 所有 # 格子在纵横方向上是连通的。
• 至少存在一个 # 格子。

样例解释 1

根据本输入样例构造出的分形如下。黑色格子的连通分量数为 $20$，因此输出 $20$。

.............#.............
............###............
............#.#............
..........#..#..#..........
.........#########.........
.........#.##.##.#.........
..........#.....#..........
.........###...###.........
.........#.#...#.#.........
....#........#........#....
...###......###......###...
...#.#......#.#......#.#...
.#..#..#..#..#..#..#..#..#.
###########################
#.##.##.##.##.##.##.##.##.#
.#.....#..#.....#..#.....#.
###...######...######...###
#.#...#.##.#...#.##.#...#.#
....#.................#....
...###...............###...
...#.#...............#.#...
.#..#..#...........#..#..#.
#########.........#########
#.##.##.#.........#.##.##.#
.#.....#...........#.....#.
###...###.........###...###
#.#...#.#.........#.#...#.#

由 ChatGPT 4.1 翻译