Problem Description

Using the given digits, form some numbers within the range $[A, B]$ such that each of these numbers is divisible by $X$.

Input Format

The first line of input contains three integers $X, A, B$.

The second line is a string of digits that can be used. A digit can be used multiple times, and no digit will appear more than once.

Output Format

Output a single integer on one line, representing how many numbers within the range $[A, B]$ can be formed using the given digits and are divisible by $X$.

Sample Input and Output

Sample Input #1

2 1 20
0123456789

Sample Output #1

10

Sample Input #2

6 100 9294
23689

Sample Output #2

111

Sample Input #3

5 4395 9999999999
12346789

Sample Output #3

0

Notes

Data Size and Constraints

• For $100\%$ of the data, it is guaranteed that $1 \le X < 10^{11}$, $1 \le A \le B < 10^{11}$.

Notes

This problem is translated from COCI2006-2007 CONTEST #6 T5 V.

见题面 Input 部分

见题面 Output 部分