フィボナッチ数列のN項目

整数 N が与えられます。
フィボナッチ数列の N 項目を出力してください。

フィボナッチ数列は次のように定義されます：

• F(1) = 0
• F(2) = 1
• F(n) = F(n−1) + F(n−2) （n ≥ 3）

入力

N

• 整数 N (1 ≤ N ≤ 50)

出力

フィボナッチ数列の N 項目を出力せよ。

入力例1

1

出力例1

0

入力例2

2

出力例2

1

入力例3

10

出力例3

34

（0,1,1,2,3,5,8,13,21,34）

ケン

ヨワモンのパートナー

ヨワモンのパートナー