Ralph and arithmetic

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

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

Output

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

Examples

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.