说明

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

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

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

输入格式

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

输出格式

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

样例

4

3