3042 - 牧场种草

农场主John新买了一块长方形的新牧场,这块牧场被划分成M行N列,每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草,供他的奶牛们享用。

遗憾的是,有些土地相当贫瘠,不能用来种草。并且,奶牛们喜欢独占一块草地的感觉,于是John不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。

John想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择?(当然,把新牧场完全荒废也是一种方案)

输入

第一行:两个整数M和N,用空格隔开。

第2到第M+1行:每行包含N个用空格隔开的整数,描述了每块土地的状态。第i+1行描述了第i行的土地,所有整数均为0或1,是1的话,表示这块土地足够肥沃,0则表示这块土地不适合种草。

输出

一个整数,即牧场分配总方案数除以100,000,000的余数。

样例

输入

2 3
1 1 1
0 1 0

输出

9

提示

对于100%的数据,有1 ≤ M ≤ 15; 1 ≤ N ≤ 15。

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题