The path to Mary’s school is a straight line paved with hexagonal tiles. The picture below shows an example of the path with 12 numbered tiles.
Mary loves mathematics. When going to school, she steps on the tiles of that path following these rules:
When classes are over, she is so tired that she avoids the path and walks on the lawn.
Mary does not want to repeat any sequence of steps on the tiles and she would like to know, if the path is paved with N numbered tiles and a tile with the face, how many days will it take to make each possible sequence once.
For example, five days will be needed for her to try all possible step sequences if the path has N = 4 tiles, one day for each of the sequences: 1-2-3-4, 1-2-4, 1-3-4, 2-3-4 and 2-4.
Write a program to determine how many different step sequences there are for a path with a given number N of tiles.
The input contains several test cases. Each test case is composed by a line containing an integer N(1 ≤ N ≤ 40), the number of tiles in the path.
The last test case is followed by a line containing a single zero.
For each test case, print a line containing a single integer, the number of different step sequences.
1 4 2 10 0
1 5 2 89