← 返回题目列表

Codeforces · 388/D

D. 狐狸和完美套装

中文机器翻译题面 查看原题

Fox Ciel 研究数论。

她认为包含非负整数的非空集合S是完美的当且仅当对于任何$$a,b\in S$$(a可以等于b),$$(a\xor\b)\inS$$。其中 xor 运算表示异或运算 (http://en.wikipedia.org/wiki/Exclusive_or)。

请计算由不大于k的整数组成的完美集合的数量。答案可能非常大,因此打印它对 1000000007 (109 + 7) 取模。

输入

第一行包含一个整数 k (0 ≤ k ≤ 109)。

输出

打印单个整数 — 所需集合的数量以 1000000007 (109 + 7) 为模。

示例

输入 #1

1

输出 #1

2

输入 #2

2

输出 #2

3

输入 #3

3

输出 #3

5

输入#4

4

输出#4

6

注意

在示例 1 中,有 2 个这样的集合:{0} 和 {0, 1}。请注意,{1} 不是完美集合,因为 1 xor 1 = 0 并且 {1} 不包含零。

在示例 4 中,有 6 个这样的集合:{0}、{0, 1}、{0, 2}、{0, 3}、{0, 4} 和 {0, 1, 2, 3}。