### COCI 2006/2007, Contest #6

## Task V

Zvonko is playing with digits again, even though his mother has warned him that he is doing too much math and should go outside to play with his friends.

In his latest game, Zvonko looks for **multiples** of an integer X, **composed only of certain digits**. A
multiple of X is any number divisible by X.

In order to ruin Zvonko's fun, his mother decided to get a program that solves the problem. Write a program that calculates how many multiples of X are between A and B (inclusive), such that, when written in decimal, they contain only certain allowed digits.

### Input

The first line of input contains three integers X, A and B (1 ≤ X < 10^{11}, 1 ≤ A ≤ B < 10^{11}).

The second line contains the allowed digits. The digits will be given with no spaces, sorted in increasing order and without duplicates.

### Output

Output the number of multiples Zvonko can make on a single line.

### Sample Tests

## Input2 1 20 0123456789 ## Output10 |
## Input6 100 9294 23689 ## Output111 |
## Input5 4395 9999999999 12346789 ## Output0 |

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** Aug 13, 2013

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...