题目背景

Ryoku 在阅读「最初之人」的笔记的时候，发现了一个有趣的运算：$\rm xor$，这个运算的输入是两个数，输出是一个数，对应的运算时将输入的两个数化为二进制，再把每一位进行比较，若相同则输出的二进制中的这一位为 $0$，否则为 $1$。

在关于运算 $\text{xor}$ 笔记的下面有一道习题。Ryoku 很快就得出了答案，她想要考考你。

题目描述

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

输入格式

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

输出格式

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

2

2

42

274

提示

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