AT_agc003_f [AGC003F] Fraction of Fractal

高桥君从妈妈那里得到了一张网格。这张网格由 $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 \leq H, W \leq 1000$ - $0 \leq K \leq 10^{18}$ - $s_{ij}$ 只可能是 `#` 或 `.`。 - 所有 `#` 格子在纵横方向上是连通的。 - 至少存在一个 `#` 格子。 ## 样例解释 1 根据本输入样例构造出的分形如下。黑色格子的连通分量数为 $20$，因此输出 $20$。 ``` .............#............. ............###............ ............#.#............ ..........#..#..#.......... .........#########......... .........#.##.##.#......... ..........#.....#.......... .........###...###......... .........#.#...#.#......... ....#........#........#.... ...###......###......###... ...#.#......#.#......#.#... .#..#..#..#..#..#..#..#..#. ########################### #.##.##.##.##.##.##.##.##.# .#.....#..#.....#..#.....#. ###...######...######...### #.#...#.##.#...#.##.#...#.# ....#.................#.... ...###...............###... ...#.#...............#.#... .#..#..#...........#..#..#. #########.........######### #.##.##.#.........#.##.##.# .#.....#...........#.....#. ###...###.........###...### #.#...#.#.........#.#...#.# ``` 由 ChatGPT 4.1 翻译