Special Numbers

문제

Number theorist Dr. J is attracted by the beauty of numbers. When we are given a natural number $a=a_1{a}_2\cdots a_{n}a\; =\; a\_1a\_2\; \backslash cdots\; a\_n$ of $nn$ digits and a natural number $kk$, $aa$ is called $kk$-special if the product of all the digits of $aa$, i.e. $a_1\cdot a_2\cdot a_3\cdots a_{n}a\_1\; \backslash cdot\; a\_2\; \backslash cdot\; a\_3\; \backslash cdots\; a\_n$ is divisible by $kk$. Note that the number $00$ is always divisible by a natural number.

For example, if $a=2349a\; =\; 2349$ and $k=12k\; =\; 12$, then the product of all the digits of $aa$, $2\cdot 3\cdot 4\cdot 9=2162\; \backslash cdot\; 3\; \backslash cdot\; 4\; \backslash cdot\; 9\; =\; 216$ is divisible by $k=12k\; =\; 12$, so the number $23492349$ is $1212$-special. If $a=2349a\; =\; 2349$ and $k=16k\; =\; 16$, then the product of all the digits of $aa$, $2\cdot 3\cdot 4\cdot 9=2162\; \backslash cdot\; 3\; \backslash cdot\; 4\; \backslash cdot\; 9\; =\; 216$ is not divisible by $k=16k\; =\; 16$, so the number $23492349$ is not $1616$-special.

Given three natural numbers $kk$, $LL$, and $RR$, write a program to output $z({10}^9+7)z\; \backslash bmod\; (10^9\; +\; 7)$ where $zz$ is the number of $kk$- special numbers among numbers in the range $[L,R][L,\; R]$.

입력

Your program is to read from standard input. The input has one line containing three integers, $kk$, $LL$, and $RR$ (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({10}^9+7)z\; \backslash bmod\; (10^9\; +\; 7)$ where $zz$ is the number of $kk$-special numbers among the numbers in the range $[L,R][L,\; R]$, where both $LL$ and $RR$ are inclusive in the range.