중복 이진 표기법

이항 힙의 이항 트리. Wikimedia, cc-by-sa

중복 이진 표기법은 이진 표기법과 비슷하지만, 각 자리에 $0$과 $1$만 허용하는 대신 $[0, t]$ 범위의 정수를 허용한다. 여기서 $t$는 주어진 상한이다. 예를 들어 $t = 2$이면 숫자 $2$를 쓸 수 있으므로 십진수 $4$를 $100$, $20$, $12$로 나타낼 수 있다. $t=1$이면 모든 수의 표현이 하나뿐이며, 그 표현은 일반적인 이진 표현이다. 일반적으로 어떤 수를 중복 이진 표기법으로 $d_l d_{l-1} \ldots d_1 d_0$라고 쓰면 이에 대응하는 십진수는 $d_l\cdot2^l + d_{l-1}\cdot2^{l-1} + \cdots + d_1\cdot2^1 + d_0\cdot2^0$이다.

중복 이진 표기법은 자리올림 없는 연산을 가능하게 하므로 하드웨어 설계와 최악 시간 복잡도 자료 구조 설계에 쓰인다. 예를 들어 표준 이항 힙에 원소를 삽입하는 연산은 최악 시간 $O(\log n)$이지만 분할 상환 시간은 $O(1)$이다. 힙에 들어 있는 원소의 총 개수를 나타내는 이진수를 증가시키는 데 최악 시간 $O(\log n)$, 분할 상환 시간 $O(1)$이 걸리기 때문이다. 이항 힙의 개별 이항 트리를 중복 이진 표현으로 나타내면 이항 힙의 삽입 최악 시간을 $O(1)$로 줄일 수 있다.

하지만 이 문제를 푸는 데 그런 정보는 필요 없다. 이 문제에서 할 일은 간단하다. 십진수 $N$과 자릿수 상한 $t$가 주어질 때, 각 자리가 $[0, t]$ 범위에 있고 앞에 불필요한 0이 없는 중복 이진 표기법으로 $N$을 나타내는 방법의 수를 세면 된다.

입력은 한 줄로 이루어지며, 두 십진 정수 $N$ ($0 \leq N \leq 10^{16}$)과 $t$ ($1 \leq t \leq 100$)가 주어진다.

각 자리가 $[0, t]$ 범위에 있고 앞에 불필요한 0이 없는 중복 이진 표기법으로 십진수 $N$을 나타내는 방법의 수를 십진수로 출력한다. 방법의 수가 매우 클 수 있으므로 답을 큰 소수 $998\,244\,353$으로 나눈 나머지를 출력한다.