数论学家 Beata 被数字之美所吸引。给定一个 $n$ 位的整数 $a = a_1 a_2 \dots a_n$ 和一个正整数 $k$，如果 $a$ 的所有数位之积（即 $a_1 \cdot a_2 \cdot a_3 \cdot \dots \cdot 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$，编写一个程序，求 $x \pmod{998\,244\,353}$，其中 $x$ 是区间 $[L, R]$ 内 $k$-特殊数的个数。

输入格式

输入包含一行，包含三个整数 $k, L$ 和 $R$ ($1 \le k \le 10^{17}, 1 \le L \le R \le 10^{20}$)。

输出格式

输出一行。该行应包含 $x \pmod{998\,244\,353}$，其中 $x$ 是区间 $[L, R]$ 内 $k$-特殊数的个数（$L$ 和 $R$ 均包含在区间内）。

样例

输入 1

5 1 20

输出 1

4

输入 2

5 50 100

输出 2

19

输入 3

15 11 19

输出 3

0