Tetris Layout Layouts

There are seven types of Tetris tetrominoes (see the image below) which can be rotated by 0°, 90°, 180°, or 270°. You are given a board with n columns and unlimited height. In the i-th column, the bottom a_i cells are already filled with blocks (so cells in rows 1 through a_i are occupied). The falling tetromino is the m-th piece. After dropping this tetromino, we require that there is no column with a "hole" – that is, in every column the occupied cells (both from the pre‐existing layout and from the tetromino) form a contiguous block starting from the bottom.

More formally, after the tetromino is dropped, in each column, if there is at least one block (either original or from the tetromino), then the occupied cells must be exactly the cells in rows 1 through H for some H. Two placements are considered different if there is at least one cell that is occupied in one placement and empty in the other.

The tetromino can be rotated (by 0°, 90°, 180°, or 270°) and translated horizontally. When dropped, the tetromino falls vertically as a whole until in every column that it covers, the lowest block of the tetromino lands exactly on top of the pre‐existing block (i.e. at row a_j + 1 in that column). In addition, the new blocks placed in any column must be consecutive starting from row a_j + 1 (so that there is no gap).

Given the board’s configuration and the index m of the falling tetromino, count the number of distinct final layouts that satisfy the above condition.

The seven tetrominoes are defined as follows (in their default orientation):

• 1. I-piece: cells at (0,0), (1,0), (2,0), (3,0).
• 2. O-piece: cells at (0,0), (1,0), (0,1), (1,1).
• 3. T-piece: cells at (0,0), (1,0), (2,0), (1,1).
• 4. S-piece: cells at (1,0), (2,0), (0,1), (1,1).
• 5. Z-piece: cells at (0,0), (1,0), (1,1), (2,1).
• 6. J-piece: cells at (0,0), (0,1), (1,0), (2,0).
• 7. L-piece: cells at (0,0), (1,0), (2,0), (2,1).

For a given tetromino (the m-th piece), consider all its distinct rotations (rotations that yield a different set of cell coordinates after normalization) and all possible horizontal placements (translations) such that the entire tetromino lies within the board (columns 1 through n). For each candidate placement, determine the unique vertical offset so that for every column j that the tetromino occupies, the lowest block in that column lands exactly at row a_j + 1. In addition, in that column the tetromino’s blocks (after dropping) must fill consecutive cells starting from row a_j + 1 (so that the final column’s blocks form a contiguous segment from the bottom). Count all placements that satisfy these conditions.

inputFormat

The first line contains two integers n and m — the number of columns on the board and the index of the falling tetromino (1 ≤ m ≤ 7).

The second line contains n non‐negative integers a₁, a₂, ..., a_n where a_i denotes the number of filled cells at the bottom of the i-th column.

outputFormat

Output one integer — the number of distinct final layouts after dropping the tetromino that satisfy the condition that in every column, the filled cells form a contiguous block from the bottom.

sample

5 1
0 0 0 0 0

7