Marina Vitaliivna's Favorite Game
Tetris is Marina Vitaliivna's favorite game. The game board consists of C columns and an unlimited number of rows.
When a piece drops, the player can rotate it by 90, 180, or 270 degrees, and then move it left or right, ensuring the piece stays entirely within the field. The piece then falls until it reaches the bottom of the field or lands on another piece. In this version of Tetris, the piece must fall so that all parts of it are either at the bottom of the field or touching other pieces from below. This means that after a part falls, there cannot be an empty square beneath it with a piece above.
For example, consider a field with six columns and initial heights (the number of already occupied squares in each column) of 2, 1, 1, 1, 0, and 1. The piece numbered 5 can fall in five different ways:
You are given the initial heights of all columns and the number of the piece that will fall onto the field. Write a program to calculate the number of different ways the piece can fall, i.e., the number of distinct field configurations that can be achieved without violating the rules.
Input format:
The first line contains two numbers C and P (1 ≤ C ≤ 100, 1 ≤ P ≤ 7) - the number of columns and the number of the piece that will fall.
The second line contains C numbers within the range [0, 100]. These represent the initial heights of the columns.
Output format:
Output the number of possible field configurations.