Allowed Digit Multiples

Time limit1sMemory limit128 MB

Summary

Count multiples of X within [A,B] whose decimal digits all come from an allowed digit set, with values up to 10^11.

Level: Hard8 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

You are given a positive integer X, a range [A, B], and a set of usable digits. Count how many multiples of X between A and B, inclusive, have a decimal representation whose every digit belongs to the given set.

Numbers are considered in their usual decimal representation, so leading zeroes are not allowed.

Input

The first line contains X, A, and B separated by spaces. (1 <= X <= 10^11, 1 <= A <= B <= 10^11)

The second line contains the usable digits in increasing order, with no duplicates.

Output

Print the number of multiples of X between A and B, inclusive, that are made only of the given digits.

Examples3

Example 1
Input
```
2 1 20
0123456789
```
Expected output
```
10
```
Example 2
Input
```
6 100 9294
23689
```
Expected output
```
111
```
Example 3
Input
```
5 4395 9999999999
12346789 
```
Expected output
```
0
```