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:

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:

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.