Генерация ключей

문제

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

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

입력

Первая строка входных данных содержит одно целое число $NN$, записанное в шестнадцатеричной системе счисления без ведущих  нулей (). Цифры, большие 9, обозначаются заглавными латинскими буквами от 'A' до 'F'.

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

출력

Выведите одно число --- остаток от деления количества различных ключей, существующих для заданных $NN$ и $KK$, на простое число $998244353998\backslash ,244\backslash ,353$.