시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB117763.636%

문제

Ральф --- второстепенный персонаж компьютерной игры, и ему надоело находиться в тени главного героя. Ральф заметил кое-что общее между его компьютерной игрой и арифметикой.

Ральф считает, что в арифметике некоторые цифры встречаются чаще других, делая все остальные цифры второстепенными. Чтобы проверить свою гипотезу, Ральф выписал все второстепенные цифры и теперь хочет узнать количество чисел от $1$ до $n$, которые не содержат второстепенных цифр в своей десятичной записи. Помогите ему это сделать.

입력

Первая строка входного файла содержит целое число $n$ ($1 \le n \le 10^{18}$).

Вторая строка содержит целое число $k$ --- количество цифр, которые Ральф считает второстепенными ($1 \le k \le 9$).

В третьей строке через пробел записаны сами второстепенные цифры $d_1, \ldots d_k$ ($0 \le d_1 < d_2 < \ldots < d_k \le 9$).

출력

В единственной строке выходного файла выведите одно число --- количество чисел от $1$ до $n$, в десятичной записи которых не встречаются второстепенные цифры.

예제 입력 1

9
2
3 4

예제 출력 1

7

예제 입력 2

1000
9
0 2 3 4 5 6 7 8 9

예제 출력 2

3

예제 입력 3

100000
8
0 1 2 5 6 7 8 9

예제 출력 3

62

노트

В первом тестовом примере подходят все числа от $1$ до $9$, кроме $3$ и $4$.

Во втором тестовом примере подходят только числа $1$, $11$ и $111$.

В третьем тестовом примере подходят все числа длиной от $1$ до $5$, состоящие только из $3$ и $4$.