#T1593. 牧场的安排
牧场的安排
题目描述
Farmer John 新买了一块长方形的牧场,这块牧场被划分成𝑀 行 𝑁 列 (1≤𝑀≤12;1≤𝑁≤12),每一格都是一块正方形的土地。FJ 打算在牧场上的某几格土地里种上美味的草,供他的奶牛们享用。遗憾的是,有些土地相当的贫瘠,不能用来放牧。并且,奶牛们喜欢独占一块草地,于是 FJ 不会选择两块相邻的土地,即:没有哪两块草地有公共边。当然,FJ 还没有决定在哪些土地上种草。
作为一个好奇的农场主,FJ 想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择。当然,把新的牧场荒废,不在任何土地上种草,也算一种方案。请你帮 FJ 算一下这个总方案数。
输入
第 1 行:两个正整数𝑀 和 𝑁,用空格隔开;
第 2 到 𝑀+1 行:每行包含𝑁 个用空格隔开的整数,描述了每块土地的状态。输入的第𝑖+1 行描述了第𝑖 行的土地。所有整数均为0 或 1,1 表示这块土地足够肥沃,0 则表示这块地上不适合种草。
输出
第 1 行:输出一个整数,即牧场分配总方案数除以 的余数。
样例
2 3
1 1 1
0 1 0
9
提示
数据范围与提示:。