Трикутник Паскаля - це числовий трикутник, по краям якого стоять одиниці, а кожне число всередині дорівнює сумі двох чисел вгору-праворуч і вгору-ліворуч. Із-за помилки набірника трикутник Паскаля виявився записаним у рядок і утворилась послідовність виду \textbf{1}, \textbf{1}, \textbf{1}, \textbf{1}, \textbf{2}, \textbf{1}, \textbf{1}, \textbf{3}, \textbf{3}, \textbf{1}, \textbf{1}, \textbf{4}, \textbf{6}, \textbf{4}, \textbf{1}, ... \InputFile Задано один рядок, який містить натуральне число \textbf{N} (\textbf{N} ≤ \textbf{600}). \OutputFile Потрібно вивести один рядок, який містить \textbf{N}-ий член утвореної послідовності.