Ральф и арифметика
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Ральф считает, что в арифметике некоторые цифры встречаются чаще других, делая все остальные цифры второстепенными. Чтобы проверить свою гипотезу, Ральф выписал все второстепенные цифры и теперь хочет узнать количество чисел от $$$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$$$, в десятичной записи которых не встречаются второстепенные цифры.

Примеры

Входные данные
9
2
3 4
Выходные данные
7
Входные данные
1000
9
0 2 3 4 5 6 7 8 9
Выходные данные
3
Входные данные
100000
8
0 1 2 5 6 7 8 9
Выходные данные
62

Примечание

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

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

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