Трикутник Паскаля

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

Із-за помилки набірника трикутник Паскаля виявився записаним у рядок і утворилась послідовність виду 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...

Вхідні дані

Задано один рядок, який містить натуральне число N (N ≤ 600).

Вихідні дані

Потрібно вивести один рядок, який містить N-ий член утвореної послідовності.

Приклади