#465. 小明爬楼梯(1)

小明爬楼梯(1)

小明很喜欢爬楼梯,但是小明腿不够长,每次小明最多只能一步跨越两个阶梯。比如他初始在楼底,跨越一个阶梯到达 11 号阶梯,或者跨越2个阶梯到达 22 号阶梯。如下图

为了选出一种最轻松的爬楼梯的方式,小明想把所有不同的到达楼顶的方式都尝试一遍。对于一共有 nn 个阶梯的楼梯,小明一共有多少总方法从楼底到达楼顶。

由于最后答案可能很大,输出最后的答案对 100007100007 取模的结果。

输入格式

第一行输入一个整数 n(1n1000)n(1≤n≤1000)

输出格式

输出最后答案对于 100007100007 取模的结果。

输出时每行末尾的多余空格,不影响答案正确性

要求使用「文件输入输出」的方式解题,输入文件为 stairs.in,输出文件为 stairs.out

样例输入

4

样例输出

5