eolymp
bolt
Try our new interface for solving problems
Problems

Ralph and arithmetic

Ralph and arithmetic

Time limit 1 second
Memory limit 128 MiB

Ralph is a minor character in a computer game, and he is tired of being in the shadow of the main character. Ralph noticed something in common between his computer game and arithmetic.

Ralph believes that in arithmetic, some numbers occur more often than others, making all other numbers secondary. To test his hypothesis, Ralph wrote down all the minor digits and now wants to know the number of numbers from 1 to n that do not contain minor digits in their decimal notation. Help him do it.

Input data

The first line contains an integer n (1n10^18). The second line contains an integer k (1k9) - the number of digits Ralph considers minor. The third line contains the minor digits d[1], ..., d[k] (0d[1] < d[2] < ... .< d[k]9).

Output data

Print one number - the number of numbers from 1 to n which decimal notation does not contain minor digits.

Examples

Input example #1
9
2
3 4
Output example #1
7
Input example #2
1000
9
0 2 3 4 5 6 7 8 9
Output example #2
3
Input example #3
100000
8
0 1 2 5 6 7 8 9
Output example #3
62

Note

In the first test, all numbers from 1 to 9 are suitable, except for 3 and 4.

In the second test, only numbers 1, 11 and 111 match.

In the third test, all numbers from 1 to 5 in length, consisting only of 3 and 4, are suitable.

Source 2018 Цикл Интернет-олимпиад для школьников, вторая командная олимпиада сезона, базовая номинация, November 10, Problem B