说明

十九世纪七十年代，有人从外地带来了一对兔子到澳大利亚。兔子瞬间患难成灾。这些小兔子每3个月就会生一对小兔子，往后的每个月都会生一对小兔子。在理想的情况下（兔子不死）。我们来算算在第N个月后澳大利亚会有多少只兔子。

输入格式

输入月份N(1<=N<=50)

输出格式

输出每个月兔子的数量，中间用空格隔开。不用考虑末尾的空格。

样例

8

1 1 2 3 5 8 13 21