题目描述

小 S 今天给你出了一道找规律题，题目如下：
有如下的数列：1，11，21，1211，111221，312211，……

小 S 问你这个数列的第 N 项是多少，而你一头雾水根本找不出规律。聪明的小 R 悄悄地告诉你是这样的：

• 上一个数是一个 1，写作 11
• 上一个数是两个 1，写作 21
• 上一个数是一个 2，一个 1，写作 1211
• 上一个数是一个 1，一个 2，两个 1，写作 111221
• …………

相信聪明的你一定可以解决这个问题。

输入格式

第一行包含一个正整数 $N$。

输出格式

一行一个正整数，表示数列的第 $N$ 项（数字可能超过长整型范围，请用数组或字符串存储）。

样例

6

312211

数据范围

对于 $100\%$ 的数据，$1 \le N \le 30$。