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}。