题目描述

已知某一栋楼上有$n$个台阶，很不幸，小明想要回家，必须跨过这$n$个台阶。但是小明是拥有大长腿，人送外号"长腿欧巴"，可以直接迈过$1$~$n$个台阶,问有多少种方案可以正好迈完全部楼梯。可能这个数字会比较大，所以对$1000000007$取模.

特别地，当$n$为$0$时，有$1$种方案.

输入格式

一个整数n.

输出格式

一个整数，表示小明上楼的方案数.

输入输出样例 #1

输入 #1

1

输出 #1

1

输入输出样例 #2

输入 #2

2

输出 #2

2

说明/提示

注意！本题时限为0.8s！

我们要相信洛谷的机子会跑的很快的。

对于100%$n$<=MAX_LONG_LONG