题目描述

某一天，你发现了一个神奇的函数 $f(x)$，它满足以下性质：

1. $f(1) = 1$
2. 当 $p$ 为质数，$c$ 为正整数时，$f(p^c) = p \oplus c$（其中 $\oplus$ 表示异或运算）
3. 当 $a$ 与 $b$ 互质时，$f(ab) = f(a)f(b)$

你看到这个函数之后十分高兴，于是想要求出：

$$\sum_{i=1}^n f(i)$$

由于结果可能很大，你只需要输出结果对 $10^9+7$ 取模的值。

---

输入格式

一行一个整数 $n$。

---

输出格式

一行一个整数，表示 $\sum\limits_{i=1}^n f(i) \bmod 1000000007$。

---

样例

样例 1

输入

6

输出

16

样例 2

输入

233333

输出

179004642

样例 3

输入

9876543210

输出

895670833

---

数据范围与提示

• 对于 $30\%$ 的数据，$n \leq 100$
• 对于 $60\%$ 的数据，$n \leq 10^6$
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^{10}$