题目描述
农夫约翰有一片长方形土地，划成M行N列的方格。他准备种玉米、养牛，不过有些格子很贫瘠，不适合种玉米。还有，牛不喜欢在一起吃，所以牛不能放在相邻的格子里。给出这块地的情况，求约翰有多少个种玉米的方案。所有方格都不种玉米也算一种方案。
输入
第一行是M和N，1≤M，N≤12。后面有M行，描述方格情况，1表示肥沃，0表示贫瘠。
提示
【样例说明】
把各块土地编号：
1 2 3
0 4 0
只开辟一块草地的话，有4种方案：选1、2、3、4中的任一块。开辟两块草地的话，有3种方案：1、3，1、4，以及3、4.选三块草地只有一种方案：1、3、4。再加把整个牧场荒废的那一种，总方案数为4+3+1+1=9种。