题目描述

一只蜜蜂在下图所示的数字蜂房上爬动，已知它只能从标号小的蜂房爬到标号大的相邻蜂房。

问从如图位置爬到 $n$ 号蜂房，有多少种爬行路线？

输入格式

一个正整数 $n$, 表示蜂房的数量

输出格式

一行一个正整数,表示爬行路线的总数

3

3

样例解释 1

$n=3$ 时：

• 1—>3
• 2—>3
• 1—>2—>3

合计 $3$ 种路线。

4

5

样例解释 2

$n=4$ 时：

• 1—>2—>4
• 2—>4
• 1—>3—>4
• 2—>3—>4
• 1—>2—>3—>4

合计 $5$ 种路线。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 30$。