题目描述

一天”code“去爬楼梯，楼梯有 N阶，上楼可以一步上一阶，也可以一步上二阶。但是第20个台阶坏了，正在装修不能踩。编一个程序，计算到达楼梯n共有多少种不同的走法。 由于最后答案可能很大，输出最后的答案对 $10^9+7$ 取模的结果。

输入格式

一个整数n，表示楼梯数。

输出格式

输出走到第n级台阶总数。

样例

1

1

2

2

3

3

数据规模与约定

对于 20% 的数据，𝑛≤10。

对于另外 30% 的数据，𝑛≤30。

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