那些年我们画格子
时间限制：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
提示
没有写明提示
题目来源
没有写明来源