학교 급식소

문제

어느 학교 급식소의 조리사들은 늘 바쁘다. 한 학년도 $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가지다.