Description

我们需要找出rbb数的个数，rbb数构造如下：
先写上一个正整数n,然后对n以下列方式处理：
1、不作任何变动；
2、在它的左边再写上一个正整数，但该正整数不能超过上一次在左边写上的正整数的一半；
3、写上数后，继续按此规则进行处理，直到不能再写正整数为止。
即一个符合条件的数可以写成a[k]a[k-1]...a[1]n(看作是字符串相连)
其中a[k]<=a[k-1]/2,a[k-1]<=a[k-2]/2,a[1]<=n/2

Format

Input

一个正整数n(n<=1000000)

Output

对于初始给定的n，可以构造出的rbb数的个数,最终结果可能会很大，所以对1e9+7取模

Sample 1

Input

6

Output

6

Limitation

1s 256MB

Hint

根据初始的6，可以构造出的rbb数是：6 16 26 126 36 136