题目描述

小珅要上一个n级的台阶,这一次，他获得了一个特异功能，每次可以跳跃任意奇数（这里指的是跳跃的距离是奇数）的阶梯。比如他初始在楼底，跨越一个阶梯到达 1 号阶梯，或者跨越 3 个楼梯到达 3号阶梯。问他上n级台阶有多少种方法?

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

输入格式

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

输出格式

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

输入样例 #1

4

输出样例 #1

3

输入样例 #2

1

输出样例 #2

1

输入样例 #3

2

输出样例 #3

1

数据范围

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