Codah ClubTrain. Submit. Improve.
Sign in
English
#0000B5

Tetris

The popular computer game Tetris is played in a field that consists of S columns and with no limited height. At each step one of the following 7 pieces is inserted in the box:


Image: tetris1

During insertion, figures in the field can be rotated at will for 90, 180 or 270 degrees. Also, at will, you can move it left or right, as long as it is entirely within the field of play. Then the figure falls under the influence of gravity until it locates at the bottom of the field or on already taken fields. In variation of Tetris invented especially for this task, figure must be placed so that all all parts of the figure are lying on the bottom of the field or on already occupied fields. Specifically, after placing the figure there should not be a field that is free, and that there exists another field above it which is occupied.


Let’s consider an example with 6 columns where initial heights of the columns (numbers represent amount of occupied fields in each column) are 2,1,1,1,0 and 1. Figure labeled with number 5 can be accommodated in five different ways:


Image: tetris2

The initial height of each column and a figure that has to be put in the box are given in input. Write a program that determines in how many ways it can be done, that is, the number of different configurations of the field that may arise after the insertion of the figure.


InputIn the first line of standard input are two integers S i F, 1 <= S <= 100, 1 <= F <= 7, the number of columns which constitute the field and label of the figure that is being inserted. In the second row is a series of S integers between 0 and 100 (strict), the initial amount of occupied fields from left to right.

OutputIn the first and only line of the standard output write the number of ways that the default figure can be located in the box.

Input:
6 5
2 1 1 1 0 1
Output:
5


Input:
5 1
0 0 0 0 0
Output:
7


Input:
9 4
4 3 5 4 6 5 7 6 6
Output:
1


Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.