Building a staircase

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.

Examples

Input	Output
5	2
11	11
212	995645335

Explanation

n = 5

ㅤ	x
x	x
x	x

ㅤ	x
ㅤ	x
ㅤ	x
x	x

Input

Output

Examples

Explanation

Constraints

To check your solution you need to sign in