Генерация ключей
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В криптографической системе «EasyCrypt» ключом может быть любое неотрицательное целое число, двоичная запись которого содержит ровно $$$K$$$ единиц, и не превосходящее заданного целого положительного числа $$$N$$$.

Вычислите, сколько различных ключей существует для заданных $$$N$$$ и $$$K$$$. Так как ответ может быть очень большим, выведите остаток от его деления на простое число $$$998\,244\,353$$$.

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

Первая строка входных данных содержит одно целое число $$$N$$$, записанное в шестнадцатеричной системе счисления без ведущих нулей ($$$1 \le N < 16^{250}$$$). Цифры, большие 9, обозначаются заглавными латинскими буквами от 'A' до 'F'.

Вторая строка содержит одно целое число $$$K$$$ — число бит в ключе, равных единице ($$$0 \le K \le 1\,000$$$).

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

Выведите одно число — остаток от деления количества различных ключей, существующих для заданных $$$N$$$ и $$$K$$$, на простое число $$$998\,244\,353$$$.

Примеры

Входные данные
1F
2
Выходные данные
10
Входные данные
31
3
Выходные данные
17