题目描述

小明的面前有一个n级的台阶，他每次可以上1阶，2阶，3阶，现在他想知道每一种上台阶的方法，请你告诉他。

具体的，请你求出有多少种上台阶的方法；对于每一种上台阶的方法，请你用数字表示每一步的台阶数，并将不同方法按字典序输出。

例如，n=3，可行方法为111，12，21,3（4种），其中12表示第一步1个台阶，第二步2个台阶，因此按字典序输出：

4

111

12

21

3

输入格式

输入一个正整数n，表示台阶数量。

输出格式

第一行输出一个数m，表示上台阶的方法数。 之后m行每行输出一个由“1”、“2”、“3”组成的字符串，表示一种上台阶的方法。

样例数据

input

3

output

4

111

12

21

3

数据规模与约定

对于100%的数据，1<=n<=15；

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$