应该要用到数组,但是思路应该是什么样子的,求解答

要在n*m的棋盘上进行染色,并且满足以下个要求:
1:每个格子必须染上颜色,且只能染上黑白两种颜色
2:对于任何一个2x2的正方形,黑色格子的个数必须为奇数
求可能的染色方案。方案数对10^9+7取模的结果。

对于任何一个正方形,黑色格子数必须为奇数
也就是要么1个,要么3个,其实是对称的
图形必然是在下面这个图形的基础上
10101
00000
10101
添加纵向或横向的1
要添加就必须整行或整列全部添加,否则就不满足条件
而如果纵向添加了1,横向就不能再添加
所以其实就是个排列组合题
你数一数一共有多少列,看可以在哪些列填充1
再数一数一共有多少行
然后到底第1行第1列到底是1还是0,会不同,要分别计算