시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB107666.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$.

예제 입력 1

1F
2

예제 출력 1

10

예제 입력 2

31
3

예제 출력 2

17