玉米田
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
玉米田
题目描述
农夫约翰的土地由 个小方格组成,现在他要在土地里种植玉米。
非常遗憾,部分土地太贫瘠,无法种植。而且,相邻的土地不能同时种植玉米,也就是说种植玉米的所有方格之间都不会有公共边缘。
现在给定土地的大小和每个方格的状况,请你求出一共有多少种种植方法。土地上什么都不种也算一种方法。
输入格式
第 1 行包含两个整数 和 。
第 到第 行,每行包含 个整数 或 ,用来描述整个土地的状况: 表示该块土地肥沃可以种植, 表示该块土地贫瘠不能种植。
输出格式
输出一行,包含一个整数,表示总种植方法数对 取模后的值。
样例输入
2 3
1 1 1
0 1 0
样例输出
9
样例解释
把肥沃的四个方格分别记为 (第一行)和 (第二行中间)。所有合法方案包括:
- 什么都不种:1 种;
- 只种一个方格:4 种;
- 种两个不相邻的方格:、、,共 3 种;
- 种三个方格:,共 1 种。
合计 种。
数据范围
对于全部测试数据,保证 ,方格只由整数 或 组成。