说明

时间限制：1 Sec 内存限制：256 MB 输入文件：number.in 输出文件：number.out

超喜欢数字 $1$ 的小明，将某个自然数 $x$ 的美观度 $V(x)$ 定义如下：

$$V(x) = x \times \text{popcount}(x)$$

其中 $\text{popcount}(x)$ 的定义是：将 $x$ 表示为二进制数时，数字 $1$ 出现的次数。例如 $\text{popcount}(23) = 4$，因为 $23$ 的二进制表示为 $10111$，其中包含 $4$ 个 $1$。

现给定一个自然数 $N$，请计算 $\displaystyle \sum_{i=1}^{N} V(i)$ 的值，并对 $10^9+7$ 取模后输出。

输入格式

一行，一个正整数 $N$。

输出格式

输出一行，包含上述求和取模后的结果。

样例

样例 1

5

23

样例说明：

各数字的 $\text{popcount}$ 值如下：

$\text{popcount}(1) = 1,\ \text{popcount}(2) = 1,\ \text{popcount}(3) = 2,\ \text{popcount}(4) = 1,\ \text{popcount}(5)=2$

求和计算：

$(1 \times 1) + (2 \times 1) + (3 \times 2) + (4 \times 1) + (5 \times 2) = 23$，因此答案为 $23$。

样例 2

30

1333

样例 3

23072602871

123456789

数据范围

对于 20% 的数据，满足 $N \le 10^6$。

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