2224 - 整数分解为2的幂
Description

任何正整数都能分解成2的幂,给定整数N,求N的此类划分方法的数量!由于方案数量较大,输出Mod 1000000007的结果。

比如N = 7时,共有6种划分方法。

7=1+1+1+1+1+1+1

=1+1+1+1+1+2

=1+1+1+2+2

=1+2+2+2

=1+1+1+4

=1+2+4

Input

输入一个数N(1 <= N <= 10^6)

Output

输出划分方法的数量Mod 1000000007

Examples

Input

7

Output

6
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 0
通过次数 0