数论学家 J 博士被数字之美所吸引。给定一个 $n$ 位的自然数 $a = a_1 a_2 \dots a_n$ 和一个自然数 $k$，如果 $a$ 的所有数位之积（即 $a_1 \cdot a_2 \cdot a_3 \dots a_n$）能被 $k$ 整除，则称 $a$ 为 $k$-特殊数。注意，数字 0 总是能被任何自然数整除。

例如，若 $a = 2349$ 且 $k = 12$，则 $a$ 的所有数位之积 $2 \cdot 3 \cdot 4 \cdot 9 = 216$ 能被 $k = 12$ 整除，因此 2349 是 12-特殊数。若 $a = 2349$ 且 $k = 16$，则 $a$ 的所有数位之积 $2 \cdot 3 \cdot 4 \cdot 9 = 216$ 不能被 $k = 16$ 整除，因此 2349 不是 16-特殊数。

给定三个自然数 $k$、$L$ 和 $R$，编写一个程序，输出 $z \pmod{10^9 + 7}$，其中 $z$ 是区间 $[L, R]$ 中 $k$-特殊数的个数。

输入格式

程序从标准输入读取数据。输入包含一行，包含三个整数 $k$、$L$ 和 $R$ ($1 \le k \le 10^{17}$, $1 \le L \le R \le 10^{20}$)。

输出格式

程序向标准输出写入数据。仅打印一行，包含 $z \pmod{10^9 + 7}$，其中 $z$ 是区间 $[L, R]$（包含 $L$ 和 $R$）中 $k$-特殊数的个数。

样例

样例输入 1

5 1 20

样例输出 1

4

样例输入 2

5 50 100

样例输出 2

19

样例输入 3

15 11 19

样例输出 3

0