该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小明刚刚爬完楼梯，消耗了不少体力。热心的邻居给了小明一堆糖果来补充能量。这些糖果摆成一排，小明决定从最左边开始吃糖果。

题目描述

有$n$颗糖果排成一排，它们的美味程度各不相同。小明每次可以吃掉最左边的一颗糖果，或者跳过最左边的一颗，直接吃掉它右边的那颗糖果（如果存在）。他想知道有多少种不同的吃糖果的方案，直到吃完所有的糖果。

注意： 糖果的美味程度不影响吃糖果的方案数，我们只关心吃糖果的顺序。

输入格式

输入一个正整数$n$，表示糖果的数量。

输出格式

输出一个整数，表示小明吃完所有糖果的不同方案数。

输入输出样例 #1

输入 #1

3

输出 #1

4

输入输出样例 #2

输入 #2

4

输出 #2

8

说明/提示

$1≤n≤30$。