Tetris

Popularna računarska igra Tetris se igra u polju koje se sastoji od S kolona i nema ograničenu visinu. U svakom koraku se jedna od sljedećih 7 figura ubacuje u polje:

Prilikom ubacivanja figure u polje, ona se može po volji rotirati za 90, 180 ili 270 stepeni, te se može po volji pomerati lijevo ili desno, ali tako da potpuno leži unutar polja za igru. Zatim figura pod dejstvom gravitacije pada sve dok se ne smesti na dnu polja ili na već zauzetim poljima. U varijanti tetrisa osmišljenoj posebno za potrebe ovog zadatka, figura se mora smestiti tako da svi delovi figure leže na dnu polja ili na već zauzetim poljima. Preciznije, nakon smeštanja figure ne sme postojati polje koje je slobodno, a da je neko drugo polje iznad njega zauzeto.

Razmotrimo primer sa 6 kolona gde su početne visine kolona (brojevi već zauzetih polja u svakoj koloni) 2, 1, 1, 1, 0 i 1. Figuru označenu brojem 5 je moguće na pet različitih načina smestiti u polje:

Zadana je početna visina svake kolone i jedna figura koju je potrebno ubaciti u polje.
Napišite program koji određuje na koliko načina se to može uciniti, tj. broj razlicitih konfiguracija polja koje mogu nastati nakon ubacivanja figure.