Description

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<b$.

Input Format

The input contains one integer $n$.

Output Format

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

2

2

42

274

Hint

[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