Tetris is a puzzle video game originally designed and programmed by Alexey Pajitnov in the Soviet Union. Alexey derived its name from the Greek numerical prefix tetra- (all of the game's pieces, known as Tetriminoes, contain four segments) and tennis, Pajitnov's favorite sport. The game (or one of its many variants) is available for nearly every video game console and computer operating system, as well as on devices such as graphing calculators, mobile phones, portable media players, PDAs, Network music players and even as an Easter egg on non-media products like oscilloscopes.

In recent years, it had made its new appearance of the two-player battle mode, where two opposing players "attack" one another by eliminating their own tetriminoes. The game had grown more and more popular, and several strategies are developed among the skilled. The most conventional strategy is simply "tetris", where a player aim to eliminate 4 rows at a time by using an "I-Tetrimino". Another option is to use T-spin, where the player triggers the so-called "T-spin" by rotating the "T-Tetrimino" into a intentionally-made hole that could not be otherwise reached by only moving the tile. One other popular strategy is "Combo Attack", where the player strive to eliminate at least one row in every continuous drops.

Shane had played the game for a long time and had mastered all the skills mentioned above. Bored as he was, he decided to practice a new strategy, which he called "All-Clear Maniac". As the name suggests, he strives to achieve an "all-clear" in no more than 10 drops starting from the beginning. An "all-clear" is a situation where the player manage to clear all the lines (tetris) in field after dropping a tetrimino, virtually leaving the field blank.

The strategy is certainly interesting and appealing, but now Shane want to know whether it is practical. He wants to calculate the probability that he will be able to do an "all-clear" within ten moves from start, factoring in the upcoming visible queue, hold slot ... etc. This tasks, however, turn out to be very tedious so he soon gives up. He decides to approximate the answer by calculating the number of different ways to "tile up" a 4 x 10 grid using tetriminoes. Since he writes program, the task poses no difficulty for him.

However, Shane is afraid that one day, if the size of the tetris play-field change, his strategy will not work anymore. So now, you have to find the number of ways to tile up a 4 x N grids for any given N.

Note: the seven tetris (which CAN be rotated) are shown below for reference: