配点 : 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