005 - ハローキティーのあずきバー工場

時間制限 1 秒 / メモリ制限 64 MB / 得点 5 / x 3 /


TLE
1sec
MLE
64MB
得点
5

問題

ある日、キティはあずきバーを販売しようと思いました。そこで、キティはあずきバー自動製作機「あずきバーつく〜る」を製作しました。あずきバーつく〜るは、徐々に生産性を高めていき、n日目には(n - $1$)日目の製造分と(n - $2$)日目の製造分の合計と同じだけあずきバーを製造できるようになりました。
しかし、キティはその日に何本のあずきバーが製造されているのかわからなくなってしまいました。そこで、キティはあなたにn日目に製造されたあずきバーの本数を求めるプログラムをかくように依頼しました。

入出力

入力

入力は以下の形式で与えられる。

n

出力

a_bern

n日目に製造されたあずきバーの本数を出力する。

制約

1 ≤ n ≤ 90
答えが符号付き64bit整数型に収まることを保証する。
1日目と2日目に製造されたあずきバーの本数はそれぞれ1本である。

入出力例

例1

入力

6

出力

8

例2

入力

90

出力

2880067194370816120