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