서버 증축

"지난 밤, 선량한 서버가 죽었습니다. 관리자는 모두 고개를 들어주세요."

회사 서버가 계속 뻗고 있다. 그제는 14층, 오늘은 3층. 서버 관리자에게 서버 다운만큼 무섭고 고된 일이 있을까? 서버 관리자인 이하는 자신이 도맡은  서버가 뻗기를 원하지 않기에 서버 용량을 늘리기로 했다.

이하는 회사로부터 용량이 $2^0$, $2^1$, ..., $2^{k-1}$인 디스크를 각 용량별로 $a$개씩 지원받았다. 이하가 받은 총 $ak$개의 디스크는 서로 구분된다. 머신러닝을 이용해 파국을 피할 수 있는 방법을 열심히 분석한 결과 서버에 정확히 용량 $n$을 증축할 때 최적의 성능을 발휘할 수 있음을 알게 되었다. 그렇다고 이하의 고민이 사그라들진 않았다. 증축할 수 있는 용량의 조합도 다양할 뿐더러, 같은 용량의 조합이라 하더라도 디스크의 조합이 다를 수도 있다. 증축에 앞서 이하는 서버 증축을 할 수 있도록 디스크를 선택하는 경우의 수를 구해보고자 한다. 그 수가 너무 커질 걸 우려해, $1048573$으로 나눈 나머지를 계산하려고 한다. $1048573 = 2^{20} - 3$은 소수이다.

첫 번째 줄에는 세 정수 $k$, $a$, $n$이 공백으로 구분되어 주어진다. ($1 \leq k \leq 40, 1 \leq a \leq 10^6, 1 \leq n \leq 10^{15}$)

이는 이하에게 용량 $2^0$, $2^1$, ..., $2^{k-1}$의 서로 다른 디스크가 $a$개씩 있으며, 증축한 용량이 정확히 $n$이 되어야 함을 뜻한다.

첫 번째 줄에 정확히 용량 $n$을 증축할 수 있도록 디스크를 선택하는 경우의 수를 $1048573$으로 나눈 나머지를 출력한다.