Fox and Perfect Sets

题意翻译

福克斯·夏尔正在学习数论。 她认为一个非负非空集合$S$是完美的，当且仅当其中任意元素$a,b\in S$（$a$可以等于$b$），且$a\bigoplus b\in S $。其中，$\bigoplus $代表异或运算，详见https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fr=aladdin 。 请计算以小于等于$k$的非负整数构成的完美集合的个数。这个答案可能会很大，所以请对$1000000007\ (10^9+7)$取模。 ## 输入输出格式 ### 输入格式： 第一行包含一个整数$k\ (0<=k<=10^9)$。 ### 输出格式： 输出一个整数，表示完美集合的个数对$1000000007\ (10^9+7)$取模后的值。 ## 说明 在样例1中，这里有两个满足条件的集合：$\{0\}$和$\{0,1\}$。其中，集合$\{1\}$并不是完美集合，这是因为$1\bigoplus1=0$,但是集合$\{1\}$中并不包含元素$0$。 在样例4中，有6个满足条件的集合：$\{0\},\{0,1\},\{0,2\},\{0,3\},\{0,4\},\{0,1,2,3\}$。 翻译提供者：David_Lei

题目描述

Fox Ciel studies number theory. She thinks a non-empty set $ S $ contains non-negative integers is perfect if and only if for any  ( $ a $ can be equal to $ b $ ), . Where operation $ xor $ means exclusive or operation (http://en.wikipedia.org/wiki/Exclusive\_or). Please calculate the number of perfect sets consisting of integers not greater than $ k $ . The answer can be very large, so print it modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出格式

输入格式

The first line contains an integer $ k $ ( $ 0<=k<=10^{9} $ ).

输出格式

Print a single integer — the number of required sets modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

1

输出样例 #1

2

输入样例 #2

2

输出样例 #2

3

输入样例 #3

3

输出样例 #3

5

输入样例 #4

4

输出样例 #4

6

说明

In example 1, there are 2 such sets: {0} and {0, 1}. Note that {1} is not a perfect set since 1 xor 1 = 0 and {1} doesn't contain zero. In example 4, there are 6 such sets: {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4} and {0, 1, 2, 3}.