問題文

高橋君は、コンピュータを相手に海戦ゲームで遊んでいます。このゲームでは、ステージによって敵の船の種類が変わっていきます。 高橋君は、イカダステージ、カヌーステージ、帆船ステージ、高速ガレー船ステージ、戦艦ステージ、空母ステージを攻略し、ついに最終の潜水艦ステージに到達しました。

ゲームは、海域に見立てた $H\\times W$ のグリッド上で行われます。敵の潜水艦は、グリッドのマスのうちのいくつかに潜んでいます。同じマスに複数の潜水艦が潜んでいることはありません。

高橋君は探知機を用いて、各列に潜んでいる敵の潜水艦の隻数を知ることができました。$i$ 列目に潜んでいる潜水艦は、合計で $A_i$ 隻です。

さて、高橋君は爆雷を $H$ 個持っています。爆雷は各行に上の行から順に $1$ 個ずつ投射することができます。行ごとに、高橋君は整数を指定します。 もしその行に潜んでいる敵の潜水艦の隻数が、その行に対して高橋君の指定した整数に等しいなら、高橋君はその行の潜水艦をすべて爆破することができます。 そうでない場合、その行の潜水艦を爆破することはできません。

高橋君は、すべての行の潜水艦をすべて爆破することのできる可能性のあるような整数の組の指定の仕方が何通りあるかが気になっています。 高橋君にかわって、そのような指定の仕方、すなわち各行に潜んでいる潜水艦の隻数の(整数 $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