Даны число \(X\) и строка \(S\), посчитайте количество чисел \(i\) от \(0\) до \(X\), таких что число \(i\) состоит только из цифр в \(S\) и \(0\). \(0\) всегда допустим в числе независимо от \(S\).

Входные данные

В первой строке даны \(X\) и \(S\) \((1 \leq X \leq 10^18, 1 \leq |S| \leq 9)\).

Выходные данные

Выведите ответ на задачу.

Примеры

Ввод 1

15 123456789

Ответ 1

16