키 생성

암호 시스템 <>에서 키는 이진 표기법으로 정확히 $K$개의 1을 포함하고 주어진 양의 정수 $N$을 넘지 않는 음이 아닌 정수이다.

주어진 $N$과 $K$에 대해 서로 다른 키가 몇 개 존재하는지 구하여라. 답이 매우 클 수 있으므로, 소수 $998\,244\,353$으로 나눈 나머지를 출력하여라.

첫 번째 줄에는 16진법으로 표기된 하나의 정수 $N$이 주어진다. 앞에 오는 0은 쓰지 않는다 ($1 \le N < 16^{250}$). 9보다 큰 숫자는 'A'부터 'F'까지의 대문자 라틴 문자로 나타낸다.

두 번째 줄에는 하나의 정수 $K$가 주어진다. $K$는 키에서 1인 비트의 수이다 ($0 \le K \le 1\,000$).

주어진 $N$과 $K$에 대해 존재하는 서로 다른 키의 수를 소수 $998\,244\,353$으로 나눈 나머지를 하나의 수로 출력한다.