시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 512 MB | 10 | 7 | 6 | 66.667% |
В криптографической системе <<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