題目描述

BERT 是個奇怪的人，爬樓梯都不乖乖乖的一次走一格，而是有時走一階，或一次走兩階。
換句話說，假設階梯有三階，那他有三種走法
一： 第一步走一階，第二步走二階。
二： 第一步走二階，第二步走一階。
三： 全程都走一階。

現在請你寫個程式，算出如果是 n 格樓梯，Bert 有幾種走法 ?

輸入格式

每行一個數字 N ，代表現在有 N 階樓梯 。(1 <= Ｎ <= 40)

輸出格式

一個數字，代表當樓梯有 N 階時答案。

Samples

["3","4"]

["3","5"]

原始資料

• Zero1 題號：b009
• Hydro 題號：Z1009
• Locale：zh_TW
• Display：open