Fibonacci Sequence

Given a non-negative integer n, generate the first n numbers of the Fibonacci sequence. The Fibonacci sequence is defined by the recurrence:

$$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \quad \text{for } n \ge 2.$$

For example, if n = 5, the first five Fibonacci numbers are: 0, 1, 1, 2, 3.

inputFormat

A single integer n (0 ≤ n). This value specifies how many Fibonacci numbers to generate.

outputFormat

Output the first n Fibonacci numbers in order, separated by a single space. If n = 0, output nothing.## sample

0