该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Huhe回到内蒙老家指导大家种红薯，他设计了一种联合种植方案：

问题描述

• 土地被划分为M×N的网格
• 部分网格的土地标记为需要休养（不可种植）
• 种植规则：
  • 不能在相邻格子同时种植（上下左右相邻）
  • 不种植也算一种合法方案
• 需要计算所有合法种植方案数，结果对100000000取模

输入格式

• 第1行：两个整数 M, N (1 ≤ M, N ≤ 12)
• 第2..M+1行：每行N个整数（0或1）
  • 1表示可种植土地
  • 0表示需休养土地（不可种植）

输出格式

• 一个整数，表示方案数模100000000的结果

样例

输入样例

2 3
1 1 1
0 1 0

输出样例

9

数据范围

• 1 ≤ M, N ≤ 12
• 时间限制：1秒
• 内存限制：256MB

样例解释

什么都不种：这是1种合法方案。

只种1块地：种(1,1)，种(1,2)，种(1,3)。种(2,2) → 共4种方案。

种2块地（注意不相邻）：

(1,1) + (1,3)（不相邻）

(1,1) + (2,2)（不相邻）

(1,3) + (2,2)（不相邻） → 共3种方案。

种3块地：

唯一可能：(1,1) + (1,3) + (2,2)

总数： 1（不种） + 4（种1块） + 3（种2块） + 1（种3块） = 9种合法方案。