Problem Description

Takahashi is playing a naval battle game against a computer. In this game, the type of enemy ships changes with each stage. Takahashi has conquered stages with rafts, canoes, sailing ships, fast galleys, battleships, and aircraft carriers, and has finally reached the final submarine stage.

The game is played on a grid of size $H \times W$ that represents a sea area. Enemy submarines are hidden in some of the grid squares. No more than one submarine can be in the same square.

Takahashi has used a detector to find out the number of enemy submarines hidden in each column. The total number of submarines hidden in the $ i $-th column is $ A_i $.

Now, Takahashi has $ H $ depth charges. He can launch one depth charge per row, starting from the top row. For each row, Takahashi specifies an integer. If the number of enemy submarines hidden in that row equals the integer specified by Takahashi, he can destroy all the submarines in that row. Otherwise, he cannot destroy the submarines in that row.

Takahashi is curious about how many ways he can specify the integers such that he has the possibility to destroy all the submarines in every row. On behalf of Takahashi, determine how many such ways of specifying integers (a tuple of $ H $ integers) exist, and output the value modulo $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ A_1 $ : $ A_W $

Output Format

Output the number of ways to specify the integers such that all submarines can be destroyed, modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

4 2
1
3

Sample Output #1

13

Sample Input #2

3 4
3
2
1
0

Sample Output #2

7

Sample Input #3

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

Sample Output #3

281268070

Notes/Hints

Constraints

• $1 \leq H, W \leq 40$
• $0 \leq A_i \leq H (1 \leq i \leq W)$
• All inputs are integers.

Sample Explanation 1

The tuples of integers that satisfy the conditions are: $ (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) $ for a total of $ 13 $ ways.

见题面 Input 部分

见题面 Output 部分