Background

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.

Problem 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