Pascal`s triangle

Pascal's triangle - is the real triangle, the edges of which are unity, and each number inside is the sum of two numbers up-to-right and up and left.

Due to an error typographer Pascal's triangle was recorded in a line and formed a kind of sequence 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...

Input

Given a string containing an integer N (N ≤ 600).

Output

You want to display a single line containing N-th member of the newly formed sequence.

Examples