Mineral Scanner

Scientists have developed a special scanner in order to search for useful mineral resources. The search area is a grid with k rows and n columns. The rows are numbered from 1 to k (top to bottom) and the columns from 1 to n (left to right). Each cell may contain a mineral resource (represented as 1) or be empty (represented as 0).

The scanner works as follows. For a starting column p (1 ≤ p ≤ n), the scanner returns the number of cells containing minerals in a staircase scanning region defined by:

$$B_p = \sum_{d=0}^{\min(k-1, p-1)} \sum_{i=1}^{k-d} x_{i,\,p-d}, $$

where \( x_{i,j} \) is 1 if the cell in row \( i \) and column \( j \) contains a mineral resource and 0 otherwise. In other words, when starting from column p, the scanner covers:

• All cells in column p,
• The first \( k-1 \) cells in column p-1,
• The first \( k-2 \) cells in column p-2,
• And so on.

A grid is called legal if the mineral placement (0/1 in each cell) produces exactly the scanned results B = [B₁, B₂, ..., B_n] for all starting columns.

Your task is to calculate the number of legal grids modulo \(10^9+7\). Note that the scanner may be faulty so that no legal grid exists; in that case, output 0.

inputFormat

The first line contains two integers k and n (k rows and n columns).

The second line contains n integers: B₁, B₂, ..., B_n, where B_p is the scanner result for starting column p.

outputFormat

Output a single integer: the number of legal grids modulo \(10^9+7\).

sample

1 3
1 0 1

1

</p>