Ryoku 与最初之人笔记

Ryoku 在阅读「最初之人」的笔记的时候，发现了一个有趣的运算：$\rm xor$，这个运算的输入是两个数，输出是一个数，对应的运算时将输入的两个数化为二进制，再把每一位进行比较，若相同则输出的二进制中的这一位为 $0$，否则为 $1$。 在关于运算 $\text{xor}$ 笔记的下面有一道习题。Ryoku 很快就得出了答案，她想要考考你。

Ryoku 向你复述了题目：求： $$\sum_{a = 0}^n \sum_{b = a + 1}^n [a\equiv b\pmod {a \text{ xor } b}]$$ 即：求满足 $a\equiv b\pmod {a \text{ xor } b}$，且 $a,b$ 均为小于等于 $n$ 的非负整数，$a<b$，的有序二元组 $(a,b)$ 个数。

输入包含一个整数 $n$。

输出包含一个整数，为上式的值，答案对 $10^9 + 7$ 取模。

2

2

42

274

**【样例 1 说明】** 符合题意的数对 $(a,b)$ 的有：$(0,1), (0,2)$。 --- **【数据规模与约定】** 对于 $20\%$ 的数据，$n\le 10^3$。 对于 $60\%$ 的数据，$n\le 10^6$。 对于 $70\%$ 的数据，$n\le 10^9$。 对于 $100\%$ 的数据，$2\le n \le 10^{18}$。