#2808. 那些年我们画格子

内存限制:128 MiB 时间限制:10 Sec

题目描述

那一年,tourist 六度六关,赢得了5个世界冠军
那一年,乔布斯的苹果,大卖了几百万台
那一年,那些年...
童年的时候,我们还很天真,我们会笑,我们会跳,我们会闹,我们还会画格子...
pty今天就在画格子。他画了一个n*m的矩阵,并且在每个格子内都涂上了颜色,颜色只有四种:’G’,’B’,’R’,’Y’。现在他想至多改变其中K个不同格子的颜色,使得对于任意的格子都与其相邻的格子颜色不同(一个格子和周围九宫格内的8个格子相邻),他想知道方案数有多少。
由于他还很天真,所以请你来帮帮他。

输入格式

第一行三个整数:n, m,k (k <= m * n)
接下来n行m列的字符矩阵(保证只会出现’G’,’B’,’R’,’Y’)

输出格式

输出方案数除以1000000007的余数。

样例

样例输入


			

2 2 2
RG
GR

样例输出


			

8
【数据规模及约定】
对于100%的数据保证:n, m <= 100

数据范围与提示