题目描述

Number theorist Dr. J is attracted by the beauty of numbers. When we are given a natural number $a=a_1a_2\dots 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_1a_2\dots 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 \le k \le 10^{17}, 1 \le L\le R\le 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.

5 1 20

4

5 50 100

19

15 11 19

0