| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 7 | 6 | 6 | 85.714% |
Ральф --- второстепенный персонаж компьютерной игры, и ему надоело находиться в тени главного героя. Ральф заметил кое-что общее между его компьютерной игрой и арифметикой.
Ральф считает, что в арифметике некоторые цифры встречаются чаще других, делая все остальные цифры второстепенными. Чтобы проверить свою гипотезу, Ральф выписал все второстепенные цифры и теперь хочет узнать количество чисел от 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ドル$.