Background

While reading the notebook of the "Primordial Person," Ryoku discovered an interesting operation: $\text{xor}$. This operation takes two numbers as input and outputs a single number. The operation involves converting the input numbers into binary, then comparing each bit. If the bits are the same, the corresponding bit in the output is $0$; otherwise, it is $1$.

Below the notes on the $\text{xor}$ operation, there was an exercise. Ryoku quickly solved it and now wants to test you.

Problem Description

Ryoku recites the problem to you: Calculate:

$$\sum_{a = 0}^n \sum_{b = a + 1}^n [a \equiv b \pmod{a \text{ xor } b}]$$

That is, find the number of ordered pairs $(a, b)$ such that $a \equiv b \pmod{a \text{ xor } b}$, both $a$ and $b$ are non-negative integers less than or equal to $n$, and $a < b$.

Input Format

The input consists of a single integer $n$.

Output Format

The output consists of a single integer, which is the value of the above expression modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

2

Sample Output #1

2

Sample Input #2

42

Sample Output #2

274

Notes

[Sample 1 Explanation]

The pairs $(a, b)$ that meet the criteria are: $(0, 1)$ and $(0, 2)$.

[Data Range and Constraints]

For $20\%$ of the data, $n \le 10^3$.
For $60\%$ of the data, $n \le 10^6$.
For $70\%$ of the data, $n \le 10^9$.
For $100\%$ of the data, $2 \le n \le 10^{18}$.

见题面 Input 部分

见题面 Output 部分