修罗王准备将他的猛兽军团放置在M*N的方格矩阵中，但是猛兽与猛兽之间不能相邻，否则它们会互相攻击，而且由于受到地形的限制，某些方格中不能放置猛兽。请问修罗王有多少种放置方案？

第一行两个整数M（0<=N<=12）和N（1<=N<=12）
接下来M行，每行N个整数，0表示不可放置，1表示可以放置。

输出方案个数（个数可能较大，取100000000的余数）

2 3
1 1 1
0 1 0

9