题目描述

已知一个楼梯有n级,小谢同学从下往上走，一步可以走一级，也可以走两级，问:他走到 第n级楼梯有多少种走法？

输入格式

一行一个正整数n,l <= n <= 90。

输出格式

一行 n 个整数，之间用一个空格隔开，表示走到第 1 级、第 2 级、……第 n 级分别有多少种走法。

样例数据

input

9

output

1 2 3 5 8 13 21 34 55

数据规模与约定

对于 30% 的数据，$n \leq 30$。

对于 60% 的数据，$n \leq 45$。

对于 100% 的数据，$n \leq 90$。

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

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