爬樓梯的走法數

題目敘述

教學大樓的樓梯共有 n 階。你從地面出發，每一步可以跨 1 階或 2 階。要走到最頂端，一共有幾種不同的走法？只要跨步的順序不同就算不同走法。

輸入格式

輸入一個整數 n。

輸出格式

輸出一個整數，代表走法總數。

限制

• 1 ≤ n ≤ 45

範例

範例 1

輸入

2

輸出

2

範例 2

輸入

3

輸出

3

說明

• 範例 1：n=2 時可以走 1+1 或 2，共 2 種。
• 範例 2：n=3 時可以走 1+1+1、1+2、2+1，共 3 種。