变化数

变化数

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

排位赛Round3

未参加
状态
已结束
规则
ACM/ICPC
题目
7
开始于
2017-08-25 13:00
结束于
2017-08-25 18:00
持续时间
5.0 小时
主持人
参赛人数
13