題目描述

東東有個嗜好，爬階梯不是一次走一階，就是一次走兩階。

換句話說，假設階梯有三階，那他有三種走法

一：第一步走一階，第二步走二階。

二：第一步走二階，第二步走一階。

三：全程都走一階。

請問，假設階梯有n階，那東東有幾種走法?

輸入格式

一個正整數 n (0 < n < 10000)，表示階梯有 n 階

輸出格式

請輸出 n 個階梯有幾種走法

Samples

["1","3","5","6"]

["1","3","8","13"]

提示

遞推數列

原始資料

• Zero1 題號：a162
• Hydro 題號：Z0162
• Locale：zh_TW
• Display：open