A - 算盤の書

Time Limit: 2 sec / Memory Limit: 64 MB


問題文

ある数学者は次の問題を考案したという。

  • 1 つがいの兎は、産まれて 2 か月後から毎月 1 つがいずつの兎を産む。
  • 兎が死ぬことはない。
  • この条件のもとで、産まれたばかりの 1 つがいの兎は 1 年の間に何つがいの兎になるか?

※つがい:オスとメスの一組


この問題は上の問題をもとにした問題です。
今、 1 つがいの産まれたばかりの兎がいるとします。
上の問題の条件と同様に兎が増えるとすると、 n ヶ月後に何つがいの兎がいるでしょう?
このとき、 n ヶ月後ちょうどに産まれた兎のつがいも数に含めます。


入力

入力は以下の形式で標準入力から与えられる。
n
  • 何ヶ月後かを表す整数 n (0 \leq n \leq 45) が 1 行で与えられる。

出力

n ヶ月後の兎のつがいの数を標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。

入力例 1

0

出力例 1

1

入力例 2

5

出力例 2

8
  • 2 ヶ月後に 1 つがい、 3 ヶ月後に 1 つがい、
    4 ヶ月後に 2 つがい、 5 ヶ月後に 3 つがいが産まれ、
    初めにいた 1 つがいと合わせて、合計 8 つがいとなる。

入力例 3

45

出力例 3

1836311903

Source Name

天下一プログラマーコンテスト2012 予選A