31. Fibonacci Series and Its Sum

Difficulty: easy · Math

Problem

The Fibonacci series starts `0, 1` and every later term is the sum of the two terms before it: `0, 1, 1, 2, 3, 5, 8, ...` Given `N`, print the first `N` terms of the series and then the sum of those `N` terms.

Input

A single line containing the integer `N`.

Output

- Line 1: the first `N` terms, separated by single spaces. - Line 2: the sum of those terms.

Example 1

Input:
5
Output:
0 1 1 2 3
7

Explanation: The first five terms are 0 1 1 2 3; their sum is 7.

Example 2

Input:
1
Output:
0
0

Explanation: Only the term 0 is printed, so the sum is 0.

Constraints

- 1 <= N <= 90

Solutions are judged against 2 sample and 10 hidden tests. Sign in to solve it · All problems