Problem Description

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

Input Format

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

The second line is a digit string, indicating the digits that can be used. A digit can be used multiple times, and the digits will not be repeated.

Output Format

Output one integer in one line, indicating how many numbers in $[A, B]$ that can be formed using the given digits are divisible by $X$.

2 1 20
0123456789

10

6 100 9294
23689

111

5 4395 9999999999
12346789

0

Hint

Constraints

• For $100\%$ of the testdata, 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。

Translated by ChatGPT 5