| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 11 | 7 | 7 | 63.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$, в десятичной записи которых не встречаются второстепенные цифры.
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$.