那些年我们画格子

时间限制:10s      空间限制:128MB

题目描述

那一年,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

提示

没有写明提示


题目来源

没有写明来源