时空限制

1S/512M

题目描述

设 $f(x)$ 为满足 $A \oplus B = x$ 且 $1 \le A, B \le x$ 的正整数对 $(A, B)$ 的数量，其中 $\oplus$ 表示按位异或运算。

给定一个正整数 $n$，求出 $\sum_{i = 1}^{n} f(i)$ 对 $10^9 + 7$ 取模后的值。

格式

输入格式

输入共一行，包含一个正整数 $n$。

输出格式

输出共一行，包含一个整数，表示 $\sum_{i = 1}^{n} f(i)$ 对 $10^9 + 7$ 取模后的值。

样例

样例输入 #1

5

样例输出 #1

4

样例解释 #1

• $f(1) = 0$：没有满足 $1 \le A, B \le 1$ 且 $A \oplus B = 1$ 的正整数对。
• $f(2) = 0$：没有满足 $1 \le A, B \le 2$ 且 $A \oplus B = 2$ 的正整数对。
• $f(3) = 2$：满足条件的正整数对有 $(1, 2)$ 和 $(2, 1)$，因为 $1 \oplus 2 = 3$ 且 $1, 2 \le 3$。
• $f(4) = 0$。
• $f(5) = 2$：满足条件的正整数对有 $(1, 4)$ 和 $(4, 1)$，因为 $1 \oplus 4 = 5$ 且 $1, 4 \le 5$。

因此，$\sum_{i = 1}^{5} f(i) = 0 + 0 + 2 + 0 + 2 = 4$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n \le 10^{18}$。