Dãy số Fibonaci được định nghĩa như sau:

~ F_1 = 1 ; ~

~ F_2 = 1 ; ~

~ F_n = F_{n-1} + F_{n-2} ; ~

Input

• Là số nguyên N (~ N \le 100 ~)

Output

• Hãy lập trình in ra dãy gồm N số Fibonacci (Không tính ~ F_0 ~)

Sample

Input #1

5

Output #1

1 1 2 3 5

Problem source: apok