You are given $3$ integers $N$, $L$ and $R$. You need to find the sum of integers $x$, such that $L \leq x \leq R$  and, $x$ and $N$ have some common divisor excluding $1$. Since this sum can be too large, print it modulo $10^9+7$.

Input Format

The input is a single line containing $3$ space separated integers $N$, $L$ and $R$.

Output Format

Print a single intger equal to the required sum modulo $10^9 + 7$.

Constraints

$1 \leq N \leq 10^{12}$

$1 \leq L \leq R \leq 10^{18}$