2224 - 整数分解为2的幂
描述

任何正整数都能分解成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

输入

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

输出

输出划分方法的数量Mod 1000000007

样例

输入

7

输出

6
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过次数 0