繁繁今天学习了二进制，繁繁觉得二进制很神奇，任何一个整数都可以由一些互不相同的2的方幂表

示，例如7的二进制是 ，所以7=4+2+1，繁繁不满足于此，繁繁在想，如果把互不相同这个

条件去掉，会有多少种方案呢？

输入格式

一行一个整数N(1<=N<=1000000)

输出格式

一个一个数，表示答案对1000000007取模的结果

数据范围

对于30%的数据，N<=300

对于50%的数据，N<=10000

对于100%的数据，1<=N<=1000000

输入样例1

7

输入样例2

8

输入样例3

9

输出样例

输出样例1

6

输出样例2

10

输出样例3

10

样例解释

对于样例1

7=4+2+1=4+1+1+1=2+2+2+1=2+2+1+1+1=2+1+1+1+1+1=1+1+1+1+1+1+1,6种方案。