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: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

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