Algorithms and Data Structures

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

  1. n = 5
      2. ㅤ
      x
      x
      x
      x
      x
      ㅤ
      x
      ㅤ
      x
      ㅤ
      x
      x
      x
 

Constraints

Time limit: 10 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue