Given n bricks, you would like to build a staircase by stacking those bricks on top of each other in neighboring columns. As itโs a staircase, you cannot have two columns of the same length. The right columns should always be higher than the ones on the left. Having those n bricks, youโd like to know how many different ways are there to construct a valid staircase.

Input

The input contains a single integer n (5 โค n โค 500).

Output

The program should print the number of different staircases possible to obtain from those bricks.