这题如果不考虑超时的问题，直接用dp做，怎么做？
如果用{a,b,c,d}表示给i个格子染色的情况，四个值分别为：目标颜色两个偶数，一偶一奇，一奇一偶，两个奇的方案数。
则给第i+1个格子染色后的状态为{2a+b+c,a+2b+d,a+2c+d,b+c+2d}
于是很容易联想到矩乘……
设计矩阵：
2 1 1 0
1 2 0 1
1 0 2 1
0 1 1 2

然后快速幂即可……a11即为答案