Problem Description

There are seven types of Tetris blocks as shown below:

These blocks can be rotated by $90$, $180$, $270$ degrees, or not rotated at all.

Given a grid with $n$ columns and unlimited height, the bottom $a_i$ rows of the $i$-th column already contain blocks (i.e., the bottom $a_i$ rows have been filled previously), and each column only has consecutive rows at the bottom filled with blocks.

The next block to fall is the $m$-th block. Determine how many placements of this block satisfy the condition that no cell is empty while the cell above it is filled. In other words, find how many placements ensure that each column only has consecutive rows at the bottom filled with blocks.

Two placements are considered different if and only if there exists a cell that is filled in one placement and empty in the other.

Input Format

The first line contains two integers, representing the number of columns $n$ and the next falling block number $m$.

The second line contains $n$ integers, where the $i$-th integer $a_i$ represents that the bottom $a_i$ rows of the $i$-th column are filled with blocks.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

6 5
2 1 1 1 0 1

Sample Output #1

5

Sample Input #2

5 1
0 0 0 0 0

Sample Output #2

7

Sample Input #3

9 4
4 3 5 4 6 5 7 6 6

Sample Output #3

1

Notes/Hints

Sample 1 Explanation

In the six diagrams below, the top-left diagram is the initial layout of the grid, and the other five diagrams show the five possible placements.

Data Constraints

For all test cases, the following constraints apply:

• $1 \leq n \leq 100$, $1 \leq m \leq 7$.
• $0 \leq a_i \leq 100$.

Notes

The problem is translated from COCI2006-2007 Regional Competition T2 TETRIS, translated by @一扶苏一.

见题面 Input 部分

见题面 Output 部分