317003 - 放置猛兽2

【题目描述】17.3 放置猛兽2（embattle2) PKU 3254 　　猛兽只能放置在一个M×N的矩阵，而且部分方格由于地形限制无法放置猛兽，请问猛兽与猛兽若不能相邻，有多少种放置方案？ 　　【输入格式】 　　 　　【输出格式】 　　 　　【输入样例】 　　 　【输出样例】 　　

第一行：两个整数M（0≤M≤12）和N（1≤N≤12） 　　接下去M行：每行包括N个用空格隔开的整数，0代表不可放置，1代表可以放置。

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