학교 급식소

어느 학교 급식소의 조리사들은 늘 바쁘다. 한 학년도 $n$일 전체의 식단을 짜야 하는데, 만들 수 있는 요리는 서로 다른 $k$가지뿐이다.

학생들은 입맛이 까다롭다. 같은 요리가 $\ell$일 연속으로 나오면 학생들은 조리사에게 반란을 일으킨다.

식단은 $n$일 각각에 요리를 하나씩 배정한 것이고, 하루라도 배정된 요리가 다르면 서로 다른 식단이다. 반란을 일으키지 않는 식단이 몇 가지인지 세어라.

첫째 줄에 세 정수 $n$, $\ell$, $k$가 공백으로 구분되어 주어진다. $n$은 날짜 수이고 ($0 \le n \le 2\,000\,000\,000$), $\ell$은 학생들의 인내심, 즉 같은 요리가 며칠 연속되면 반란이 일어나는지를 나타내는 값이며 ($2 \le \ell \le 200$), $k$는 만들 수 있는 요리의 가짓수이다 ($1 \le k \le 100$).

반란을 피하는 식단의 개수를 $4\,000\,000\,009$로 나눈 나머지를 한 줄에 출력한다. $n = 0$이면 빈 식단 하나만 존재하므로 답은 $1$이다.

$n = 3$, $\ell = 2$, $k = 3$이면 조건을 만족하는 식단은 다음 12가지다.

1 2 1
1 2 3
1 3 1
1 3 2
2 1 2
2 1 3
2 3 1
2 3 2
3 1 2
3 1 3
3 2 1
3 2 3