003 - フィボナッチ数列

問題

フィボナッチ数列
フィボナッチ数列は
F₀=0
F₁=1
F_n=F_n-1+F_n-2
で定義された数列です。 n番目のフィボナッチ数列を出力するプログラムを作りなさい。（出来れば再帰でやってね）

入力

N

1行目に求めたいフィボナッチ数列の番号Nが与えられる

出力

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

制約

全ての入出力ケースについて以下を満たす。

• 1 ≦ N ≦ 30

入出力例

入力例1

6

出力例1

8

入力例2

1

出力例2

1

入力例3

25

出力例3

75025