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

В криптографической системе <<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$.