30861번 - Special Numbers 다국어

문제

Number theorist Dr. J is attracted by the beauty of numbers. When we are given a natural number $a = a_1a_2 \cdots a_n$ of $n$ digits and a natural number $k,ドル $a$ is called $k$-special if the product of all the digits of $a,ドル i.e. $a_1 \cdot a_2 \cdot a_3 \cdots a_n$ is divisible by $k$. Note that the number 0ドル$ is always divisible by a natural number.

For example, if $a = 2349$ and $k = 12,ドル then the product of all the digits of $a,ドル 2ドル \cdot 3 \cdot 4 \cdot 9 = 216$ is divisible by $k = 12,ドル so the number 2349ドル$ is 12ドル$-special. If $a = 2349$ and $k = 16,ドル then the product of all the digits of $a,ドル 2ドル \cdot 3 \cdot 4 \cdot 9 = 216$ is not divisible by $k = 16,ドル so the number 2349ドル$ is not 16ドル$-special.

Given three natural numbers $k,ドル $L,ドル and $R,ドル write a program to output $z \bmod (10^9 + 7)$ where $z$ is the number of $k$- special numbers among numbers in the range $[L, R]$.

입력

Your program is to read from standard input. The input has one line containing three integers, $k,ドル $L,ドル and $R$ (1ドル ≤ k ≤ 10^{17},ドル 1ドル ≤ L ≤ R ≤ 10^{20}$).

출력

Your program is to write to standard output. Print exactly one line. The line should contain $z \bmod (10^9 + 7)$ where $z$ is the number of $k$-special numbers among the numbers in the range $[L, R],ドル where both $L$ and $R$ are inclusive in the range.

제한

힌트