← 返回题目列表

AtCoder · colopl2018_final_e

E. 高桥队长

中文机器翻译题面 查看原题

配点 : 1100 点

問題文

高桥正在和电脑玩海战游戏。在这个游戏中,敌舰的类型根据阶段而变化。 高桥完成了木筏阶段、独木舟阶段、帆船阶段、高速厨房阶段、战列舰阶段、航空母舰阶段,最后到达了最后的潜艇阶段。

游戏被比作一片海域。 它是在 H\times W 的网格上完成的。敌方潜艇潜伏在网格的某些方格中。同一方格内不能隐藏多艘潜艇。

使用探测器,高桥能够确定每排潜伏的敌方潜艇数量。i 潜伏在行中的潜艇总数 A_i 这是一艘船。

现在,高桥先生,深水炸弹 我有 H 件。深水炸弹从顶部开始放置在每一行中。 1 可以一一投影。高桥为每一行指定一个整数。 如果该排潜伏的敌方潜艇数量等于高桥为该排指定的整数,高桥就可以炸毁该排的所有潜艇。 如果没有,你就无法炸毁那一排的潜艇。

Takahashi 想知道有多少种方法来指定一组整数,这些整数可能会炸毁所有行中的所有潜艇。 高桥先生,我想解释一下如何指定这样一个方法,即每排潜伏的潜艇数量(整数) 找到对的数量(由 H 块组成)并计算值。 求出除以 10^9+7 的值。

制約

  • 1 \leq H,W \leq 40
  • 0 \leq A_i \leq H(1\leq i\leq W)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

H W
A_1
:
A_W

出力

计算指定一组可以炸毁所有潜艇的整数的可能方法的数量。 打印除以 10^9+7 后的余数。


入力例 1

4 2
1
3

出力例 1

13

满足条件的一组整数是(0,1,1,2),(0,1,2,1),(0,2,1,1),(1,0,1,2),(1,0,2,1),(1,1,0,2),(1,1,2,0),(1,2,0,1),(1,2,1,0),(2,0,1,1),(2,1,0,1),(2,1,1,0),(1,1,1,1) 的 13 是的。


入力例 2

3 4
3
2
1
0

出力例 2

7

入力例 3

10 10
3
1
4
1
5
9
2
6
5
3

出力例 3

281268070