题目描述

Aki正站在一段共有 $n$ 级台阶的楼梯下方，准备一路跑到最上面。

每一步他只能选择下面两种走法之一：

• 向上走 $1$ 级台阶；
• 向上走 $2$ 级台阶。

请你计算：从地面出发，恰好走到第 $n$ 级台阶，一共有多少种不同的走法。由于答案可能很大，请对 $10^9+7$ 取模后输出。

输入格式

输入一行，一个整数 $n$。
数据范围：$1 \le n \le 2000$。

输出格式

输出一行，一个整数，表示不同走法数对 $10^9+7$ 取模后的结果。

5

8

Hint

样例解释： 到达第 $5$ 级台阶的走法共有 $8$ 种。若把一次走 $1$ 级记为 1，一次走 $2$ 级记为 2，则这 $8$ 种走法分别为：

11111
1112
1121
1211
2111
122
212
221