Треугольник Паскаля

Треугольник Паскаля - это числовой треугольник, по краям которого стоят единицы, а каждое число внутри равно сумме двух чисел вверх-вправо и вверх-влево.

Из-за ошибки наборщика треугольник Паскаля оказался записанным в строчку и образовалась последовательность вида 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...

Входные данные

Дана одна строка, содержащая натуральное число N (N ≤ 600).

Выходные данные

Требуется вывести одну строку, содержащую N-ый член образовавшейся последовательности.

Примеры