# Description

Luogu 传送门

说实话我感觉这题说的还挺迷的，看了好久题意才看懂 QwQ

这里稍微解释一下吧，就是初始的时候给你一个字符矩阵，上面有黑白两种格子，保证黑格子四联通。

然后你需要扩展这个字符矩阵。

简单来说，假设当前矩阵为 $k$ 级矩阵，要扩展成 $k + 1$ 级矩阵，我们把黑格子变成当前字符矩阵（ $k$ 级矩阵）的样子，白格子就变成当前字符矩阵大小的全白格子。

这是样例一的 2 级分形：

最后计算 $k$ 级分形的黑色格子连通块个数

# Solution

我们要考虑一下每次扩展之后会多出来哪些黑色连通块，又有哪些黑色连通块会彼此连在一起。

分类讨论：

样例一属于左右会相连，上下不相连的情况。

连通块个数从 1 变为了 4。

简单推一下规律，~~不难发现~~：

$连通块个数 = 原图黑色格子个数 - 左右相邻都是黑色格子的对数$

然后我们再扩展一次，发现这个结论还是对的！

那么这个东西如何计算呢？

设 $a_k$ 表示黑色格子个数， $b_k$ 表示总的相邻黑点对数， $c_k$ 表示拼接时两个相邻的大块之间形成的黑色点对数。

$a_k = a_{k - 1} \times a_{k - 1}\\ b_k = b_{k - 1} \times a_{k - 1} + b_{k - 1} \times c_{k - 1}\\ c_k = c_{k - 1} \times c_{k - 1}$

第一条式子和第三条式子应该不难理解吧。

第二条：原本有的相邻黑点对数在所有黑点扩展出的图形中都会出现一遍（ $b_{k - 1} \times a_{k - 1}$ ），然后再加上边界上出现的次数（ $b_{k - 1} \times c_{k - 1}$ 这个可以手推一下）。

于是我们就得到了递推式子。

不难发现，这东西可以矩阵快速幂优化一下。矩阵长这个样子：

$\begin{vmatrix}a&b\\0&c\end{vmatrix}$

快速幂计算它的 $k - 1$ 次方即可。

	#include <bits/stdc++.h>
	#define ll long long

	using namespace std;

	const int N = 1010;
	const int mod = 1e9 + 7;
	int n, m;
	ll k;
	char t[N];
	int s[N][N];

	inline int qpow(int a, ll b){
	int res = 1;
	while(b){
	if(b & 1) res = 1ll * res * a % mod;
	a = 1ll * a * a % mod, b >>= 1;
	}
	return res;
	}

	/*
	\|a,b\|
	\|0,c\|
	*/
	struct matrix{
	int a, b, c;

	matrix(int _a = 0, int _b = 0, int _c = 0) {a = _a, b = _b, c = _c;}

	friend matrix operator * (matrix A, matrix B){
	matrix C;
	C.a = 1ll * A.a * B.a % mod;
	C.b = (1ll * A.a * B.b + 1ll * A.b * B.c) % mod;
	C.c = 1ll * A.c * B.c % mod;
	return C;
	}

	matrix operator ^ (ll p) const{
	matrix r(1, 0, 1), B(a, b, c);
	for(; p; B = B * B, p >>= 1)
	if(p & 1) r = r * B;
	return r;
	}
	}f;

	int main(){
	scanf("%d%d%lld", &n, &m, &k);
	if(!k) return puts("1"), 0;
	for(int i = 1; i <= n; ++i){
	scanf("%s", t + 1);
	for(int j = 1; j <= m; ++j)
	s[i][j] = (t[j] == '#');
	}
	int cnt = 0, ud = 0, lr = 0, UD = 0, LR = 0;
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= m; ++j){
	cnt += s[i][j];
	if(i == 1) UD += s[1][j] & s[n][j];
	else ud += s[i][j] & s[i - 1][j];
	if(j == 1) LR += s[i][1] & s[i][m];
	else lr += s[i][j] & s[i][j - 1];
	}
	if(!UD && !LR) printf("%d\n", qpow(cnt, k - 1));
	else if(UD && LR) puts("1");
	else{
	if(UD) f = matrix(cnt, ud, UD) ^ (k - 1);
	else f = matrix(cnt, lr, LR) ^ (k - 1);
	printf("%d\n", (f.a - f.b + mod) % mod);
	}
	return 0;
	}