2153: 宝典2第十一章猛兽军团2

【题目描述】猛兽军团2（embattle2.cpp/c/pas )PKU 3254

　　事实证明，理想和现实总是存在差距，修罗王到了战场才发现，猛兽军团只能放置在一个M×N的矩阵，而且部分方格由于地形限制无法放置猛兽，请问猛兽与猛兽若不能相邻，有多少种放置方案（注：经过修罗王的三观教育，猛兽之间的关系略显缓和，但仍不能彼此相邻）？

　　【输入格式】

　　第一行：两个整数M(0≤M≤12) 和N(1≤N≤12)

　　接下去M行：每行包括N个用空格隔开的整数，0代表不可放置，1代表可以放置。

　　【输出格式】

　　放置方案个数（个数可能较大，取100000000的余数）

　　【输入样例】

　　2 3

　　1 1 1

　　0 1 0

  　【输出样例】

　　　9