P6034 Ryoku and the Notes of the First Person

When Ryoku was reading the notes of the “First Person”, she found an interesting operation: $\rm xor$. This operation takes two numbers as input and outputs one number. It works by converting the two input numbers into binary, then comparing each bit: if the bits are the same, that bit in the output is $0$; otherwise it is $1$. Below the notes about the $\text{xor}$ operation, there is an exercise. Ryoku quickly got the answer, and she wants to test you.

Ryoku retold the problem to you: compute: $$\sum_{a = 0}^n \sum_{b = a + 1}^n [a\equiv b\pmod {a \text{ xor } b}]$$ That is, count the number of ordered pairs $(a,b)$ such that $a\equiv b\pmod {a \text{ xor } b}$, where $a,b$ are non-negative integers not greater than $n$, and $a

The input contains one integer $n$.

Output one integer, the value of the expression above, modulo $10^9 + 7$.

**[Sample 1 Explanation]** The pairs $(a,b)$ that satisfy the condition are: $(0,1), (0,2)$. --- **[Constraints]** For $20\%$ of the testdata, $n\le 10^3$. For $60\%$ of the testdata, $n\le 10^6$. For $70\%$ of the testdata, $n\le 10^9$. For $100\%$ of the testdata, $2\le n \le 10^{18}$. Translated by ChatGPT 5