도망친 게 아니라, 빛이 드는 곳으로 갔을 뿐이야

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

우정 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$ 중 작지 않은 쪽의 수이다.