1719: 站岗方案数
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：33
Solved：16
Description
指挥员要在n*m的网格阵地上布置战士去站岗，这些网格上有的己放置了火炮(用0表示)，而没有放置火炮的，则可以布置站岗(用1表示)。指挥员要求在相邻的网格上不要同时设岗。请你编程求出总共有多少种布置战士站岗的方案（注意没有一个战士去站岗也是一种方案）。
Input
输入第 1 行: 两个正整数 n 和 m ，用空格隔开
输入第 2..n+1 行: 每行包含 m 个用空格隔开的整数，描述了每网格阵地的状态。所有整数均为 0 或 1 ，是 1 的话，表示可以布置站岗，0 则表示己放置了火炮。
输入第 2..n+1 行: 每行包含 m 个用空格隔开的整数，描述了每网格阵地的状态。所有整数均为 0 或 1 ，是 1 的话，表示可以布置站岗，0 则表示己放置了火炮。
Output
输出一个整数，即布置战士站岗的不同方案总数除以 100,000,000 的余数。
Sample Input Copy
2 3
1 1 1
0 1 0
Sample Output Copy
9
HINT
10=<n,m<=10