Description

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)$ 个数。

Input Format

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

Output Format

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

2

2

42

274

Hint

【样例 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}$。