#C. 阿Q爬楼梯(2)

    Type: Default 1000ms 256MiB

阿Q爬楼梯(2)

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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

3021.png

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

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

输入格式

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

输出格式

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

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

样例输入

4

样例输出

3

金牛周日9:00 阶段测试

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
7
Start at
2023-12-17 9:00
End at
2023-12-17 11:00
Duration
2 hour(s)
Host
Partic.
3