那些年我们画格子

那一年，tourist 六度六关，赢得了 $5$ 个世界冠军；那一年，乔布斯的苹果大卖了几百万台；那一年，我们还很天真，会笑、会跳、会闹，也会画格子。

今天，pty 画了一个 $n\times m$ 的矩阵，并为每个格子涂上了颜色。颜色共有 $4$ 种，分别为 G、B、R、Y。

现在，他想改变至多 $k$ 个不同格子的颜色，使得任意两个相邻格子的颜色均不相同。若两个格子位于同一个 $3\times 3$ 九宫格中且不重合，则称它们相邻，即每个格子至多与周围 $8$ 个格子相邻。

请计算满足条件的方案数。

输入格式

第一行输入 $3$ 个整数 $n,m,k$。

接下来输入 $n$ 行，每行包含 $m$ 个字符，表示初始颜色矩阵。每个字符均为 G、B、R、Y 之一。

输出格式

输出满足条件的方案数对 $10^9+7$ 取模后的结果。

样例输入

2 2 2
RG
GR

样例输出

8

数据范围

• $k\le n\times m$；
• 输入矩阵中的字符只可能为 G、B、R、Y。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

2 2 2
RG
GR

输出

8