Snooker#469

Snooker

1 second
64 megabytes
Medium

Snooker is a variety of billiards involving two players. They take turns approaching the table and potting balls according to certain rules. If a shot follows all the rules, the player earns points for that shot and is allowed to make the next shot. This continues until all balls on the table are gone. If a shot breaks the rules, the player scores no points for it, and the turn passes to the other player. A sequence of correct shots is called a series. It is given that after the start of the game, the player's first series totaled points. You are to find out in how many different ways this series could occur. Two ways are considered different if they differ in any shot. Shots are considered different if the set of balls potted during the shot is different. Balls of the same color are considered identical and indistinguishable.

Rules.

At the beginning of the game, there are red balls and colored balls (one of each color) on the table.

Each potted red ball scores point. Colored balls score the following points: yellow — , green — , brown — , blue — , pink — , black — .

If the game has just begun, it is allowed to pot one or more red balls; colored balls cannot be potted. The potted red balls are removed from the table. Points scored for this shot equal the number of red balls potted.

If the previous shot potted a red ball or several red balls, it is allowed to pot any one colored ball; red balls cannot be potted. The potted colored ball is returned to the table. Points scored for this shot equal the value of the colored ball.

If the previous shot potted a colored ball and there are still red balls on the table, it is allowed to pot one or more red balls; colored balls cannot be potted. The potted red balls are removed from the table. Points scored for this shot equal the number of red balls potted.

If the previous shot potted a colored ball and only colored balls remain on the table, it is allowed to pot the lowest value colored ball present on the table. No other balls may be potted in this shot. The potted ball is removed from the table. Points scored for this shot equal the value of the potted colored ball.

Input

The first line contains one integer (1 \leq N \leq 147).

Output

Print a single number — the number of different ways to start the game with a series of points.

Examples

Example 1

Loading
Loading