目录

题目?

题解

题目?

• ?1000ms
• ?32767K

蒜头君很喜欢爬楼梯，这一次，他获得了一个特异功能，每次可以跳跃任意奇数的阶梯。比如他初始在楼底，跨越一个阶梯到达?1?号阶梯，或者跨越?3?个楼梯到达?3?号阶梯。如下图

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

由于最后答案可能很大，输出最后的答案对?100007?取模的结果。

输入格式

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

输出格式

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

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

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

样例输入复制

4

cs