Ralph and Arithmetic

Interview

Time limit2sMemory limit1024 MB

Summary

Count the integers from 1 to n (n up to 10^18) whose decimal digits avoid every digit in a given set of minor digits.

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

Problem

Ralph is a minor character in a computer game, and he is tired of standing in the shadow of the main hero. Ralph noticed something that his game and arithmetic have in common.

Ralph believes that in arithmetic some digits appear more often than others, which makes all the other digits minor. To test his hypothesis, Ralph wrote down all the minor digits and now wants to know how many numbers from $1$ to $n$ do not contain any minor digit in their decimal notation. Help him count them.

Input

The first line contains an integer $n$ ( $1 \le n \le 10^{18}$ ).

The second line contains an integer $k$ , the number of digits Ralph considers minor ( $1 \le k \le 9$ ).

The third line contains the minor digits $d_1, \ldots, d_k$ , separated by spaces ( $0 \le d_1 < d_2 < \ldots < d_k \le 9$ ).

Output

Print one number: the count of integers from $1$ to $n$ whose decimal notation contains no minor digits.

Hint

In the first test, every number from 1 to 9 works except 3 and 4.

In the second test, only 1, 11, and 111 work.

In the third test, every number of length 1 to 5 made only of the digits 3 and 4 works.

Examples3

Example 1
Input
```
9
2
3 4
```
Expected output
```
7
```
Example 2
Input
```
1000
9
0 2 3 4 5 6 7 8 9
```
Expected output
```
3
```
Example 3
Input
```
100000
8
0 1 2 5 6 7 8 9
```
Expected output
```
62
```