一个N*M的矩阵，每个格子是0或者1，1表示土壤肥沃可以种植草地，0则不可以。在种草地的格子可以放牛，但边相邻的两个格子不允许同时放牛，问总共有多少种放牛的方法？
(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)
Line 1: Two space-separated integers:
N and M
Lines 2..N+1: Line
i+1 describes row
i of the pasture with
M space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)
2 3 1 1 1 0 1 0
9