分数: 1700 点
问题陈述
Snuke 从他母亲那里得到了一个网格,作为生日礼物。网格有 H 行和 W 列。每个单元都被漆成黑色或白色。所有黑色单元格都是 4-连接,即只需访问黑色单元格就可以从任意黑色单元格遍历到任意其他黑色单元格,其中只允许水平或垂直移动。
处单元格的颜色 i第行和 j第列 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 用一个字符表示 s_{ij}。如果 s_{ij} is #,电池被漆成黑色。如果 s_{ij} is .,单元格被漆成白色。至少有一个单元被漆成黑色。
我们将定义 分形 如下。 的分形 级别 0 是 1 × 1 带有黑色单元格的网格。 水平分形 k+1 是通过将较小的网格排列在 H 行和 W 列,遵循 Snuke 网格的图案。 在与 Snuke 网格中的黑色单元相对应的位置处,存在级别分形的副本 已放置 k 。 在与 Snuke 网格中的白色单元相对应的位置处,该网格的单元都是白色的,其尺寸与水平分形相同 k已放置。
您将获得 Snuke 网格的描述,以及一个整数 K。求水平分形中黑色单元格连通分量的数量 K,模数 10^9+7.
约束
- 1 ≦ H,W ≦ 1000
- 0 ≦ K ≦ 10^{18}
- 每个 s_{ij} 是
#or.. - 给定网格中的所有黑色单元格都是 4 连接的。
- 给定网格中至少有一个黑色单元格。
输入
输入由标准输入按以下格式给出:
H W K
s_{11} .. s_{1W}
:
s_{H1} .. s_{HW}
输出
打印水平分形中黑色单元格的连通分量数 K,模数 10^9+7.
示例输入 1
3 3 3 .#. ### #.#
示例输出 1
20
水平的分形 这种情况下的 K=3 如下所示。有 20 黑色单元格的连接组件。
.............#............. ............###............ ............#.#............ ..........#..#..#.......... .........#########......... .........#.##.##.#......... ..........#.....#.......... .........###...###......... .........#.#...#.#......... ....#........#........#.... ...###......###......###... ...#.#......#.#......#.#... .#..#..#..#..#..#..#..#..#. ########################### #.##.##.##.##.##.##.##.##.# .#.....#..#.....#..#.....#. ###...######...######...### #.#...#.##.#...#.##.#...#.# ....#.................#.... ...###...............###... ...#.#...............#.#... .#..#..#...........#..#..#. #########.........######### #.##.##.#.........#.##.##.# .#.....#...........#.....#. ###...###.........###...### #.#...#.#.........#.#...#.#
示例输入 2
3 3 3 ### #.# ###
示例输出 2
1
示例输入 3
11 15 1000000000000000000 .....#......... ....###........ ....####....... ...######...... ...#######..... ..##.###.##.... ..##########... .###.....####.. .####...######. ############### #.##..##..##..#
示例输出 3
301811921