31742번 - 도망친 게 아니라, 빛이 드는 곳으로 갔을 뿐이야 서브태스크

"도망친 게 아니야. 빛을 찾아간 거야."

우정 2관 사감실에 있는 특별한 기계를 아는가? 해당 기계에 $n$에 해당하는 값을 설정하고 수를 입력하면 아래 순서도에 따라 수를 출력하는 원리이다.

예를 들어, 기계의 $n$을 $3$으로 설정하고, 사용자가 입력한 값이 $731$이라면 아래와 같이 동작한다.

1. $731$을 $3$으로 나누면 약 $243.67(=x)$이므로 $x$는 정수가 아니며, 해당 값을 반올림하면 $244$이다.
2. 기계의 $a$ 값은 $244$로 바뀐다.
3. $244$를 $3$으로 나누면 약 $81.33(=x)$이므로 $x$는 정수가 아니며, 해당 값을 반올림하면 $81$이다.
4. 기계의 $a$ 값은 $81$로 바뀐다.
5. $81$을 $3$으로 나누면 $27(=x)$이므로 $x$는 정수이며, 따라서 $a$는 $27$로 바뀌고, 해당 값이 출력된다.
6. 기계의 동작이 종료된다.

즉, 위와 같은 설정과 입력값에 대해서는 $27$이 출력되는 것이다.

똑똑한 경곽이는 세 양의 정수 $p$, $q$, $r$을 생각하고, 기계의 $n$을 $p$로 설정하기로 했다. 이후, $1$ 이상 $p^q$ 미만의 정수 중, 위 기계에 입력할 때 기계의 동작이 유한 번의 시행 내에 종료되면서 출력값이 $r$이 되는 수의 개수가 궁금해졌다. 경곽이가 직접 모든 수를 넣어보기 전에 개수를 찾는 것을 도와주자.

첫 번째 줄에 $p$, $q$, $r$ 이 공백으로 구분되어 주어진다.

첫 번째 줄에 기계의 동작이 유한 번의 시행 내에 종료되면서 출력값이 $r$이 되는 수의 개수를 $1,000,000,009$ ($1,000,000,007$이 아님에 유의하라)로 나눈 나머지를 출력한다.

• $2\le{p}\le10^6$, $1\le{q}\le10^6$, $0\le{r}\le10^9$이다.
• $p$, $q$, $r$은 음이 아닌 정수이다.

• 반올림은 다음과 같이 정의된다: 어떤 수 $x$를 반올림하여 $y$가 되었다면, $y$는 $x$와 차가 가장 작은 정수(들) 중 최댓값이다.
• 차는 다음과 같이 정의된다: $x$와 $y$의 차는 $x-y$와 $y-x$중 작지 않은 수이다.