P83042

牧场种草

难度 7 级 初三 动态规划入门 状态压缩
讨论 统计 31通过 101提交 30.7%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

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

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

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

输入

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

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

输出

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

样例

样例 1
输入
2 3
1 1 1
0 1 0
输出
9

提示

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

来源

动规专题

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交