问题陈述

Snuke从他妈妈那里得到了一个网格作为生日礼物。网格有$H$行和$W$列。每个单元格都是黑色或白色的。所有黑色单元格都是_4连接_的，也就是说，可以通过访问黑色单元格从任何一个黑色单元格遍历到任何其他黑色单元格，只允许在水平或垂直方向上移动。

第$i$行和第$j$列$(1 ≦ i ≦ H, 1 ≦ j ≦ W)$处的单元格的颜色用字符$s_{ij}$表示。如果$s_{ij}$是#，则单元格被涂成黑色。如果$s_{ij}$是.，则单元格被涂成白色。至少有一个单元格被涂成黑色。

我们将定义以下内容为_分形_。级别$k$的分形是一个由较小的网格按照Snuke网格的模式排列成$H$行和$W$列的位置。对应于Snuke网格中的黑色单元格的位置放置级别$k$的分形的副本。对应于Snuke网格中的白色单元格的位置，放置一个尺寸与级别$k$的分形相同的所有单元格都为白色的网格。

给定Snuke网格的描述和整数$K$。找到级别为$K$的分形中黑色单元格的连通分量数量，取模$10^9+7$。

约束条件

• $1 ≦ H,W ≦ 1000$
• $0 ≦ K ≦ 10^{18}$
• 每个$s_{ij}$要么是#要么是.。
• 给定网格中的所有黑色单元格都是4-connected的。
• 给定网格中至少有一个黑色单元格。

输入

输入以以下格式从标准输入给出：

$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