问题文

高桥君正在和电脑玩海战游戏。在这个游戏中，敌方船只的类型会随着关卡的不同而改变。高桥君已经攻略了木筏关卡、独木舟关卡、帆船关卡、快速加列舰关卡、战舰关卡和航母关卡，最终到达了最后的潜水艇关卡。

游戏是在一个 $H\\times W$ 的网格上进行的，模拟海域。敌方的潜水艇隐藏在网格的某些方格中，同一个方格中不会有多艘潜水艇。

高桥君使用探测器可以知道每一列中隐藏的潜水艇的数量。在第 $i$ 列隐藏的潜水艇数量总共为 $A_i$ 艘。

现在，高桥君有 $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