Let us call a number interesting if it is divisible by P and each of its digit is equal to some digit of the interesting set. You are given the interesting set and the number P, you need to calculate the count of interesting numbers between two given values L and R (inclusive).

Input:

First line of input contains 4 space separated integers P, L, R and Z. Here P, L and R are as defined in the problem statement, and Z is the size of the interesting set. Next line contains Z space separated integers, where the $i^{th}$ integer $F_i$ represents the $i^{th}$ number of the interesting set.

Output:

Print the count of interesting numbers in the range L to R inclusive.

Constraints:

$1 \le L \le R \le 10^{18}$

$1 \le P \le 10^5$

$1 \le Z \le 10$

$0 \le F_i \le 9$