Description

斐波那契数列（Fibonacci sequence）又称黄金分割数列，

斐波那契数列的定义如下:

$$F(0) = 1, F(1) = 1, F(n) = F(n - 1) + F(n - 2) (n \geq 2, n \in N^*) $$

Format

Input

一个整数 $n$

Output

斐波那契数列前 $n$ 项的和

Tips

C选手请使用高精度算法

Py选手请随意

请不要使用递归

(因为n=1000时答案就有200多位了，所以上限才设1000)

Samples

5

12

Limitation

$0 \leq n \leq 10^3$

1s, 1024KiB for each test case.