2153: 宝典2第十一章猛兽军团2
Memory Limit：128 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：8
Solved：3
Description
【题目描述】猛兽军团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