School Canteen

The cooks in a school canteen are always busy. They have to plan the menu for all $n$ days of the school year, and they can make only $k$ different meals.

The students are picky eaters. If the same meal is served on $\ell$ days in a row, the students rebel against the cooks.

A menu assigns one meal to each of the $n$ days, and two menus are different if any single day gets a different meal. Count the menus that avoid a rebellion.

The first line contains three space separated integers $n$, $\ell$ and $k$. $n$ is the number of days ($0 \le n \le 2\,000\,000\,000$), $\ell$ is the impatience of the students, that is, how many repeats of a single meal in a row make them rebel ($2 \le \ell \le 200$), and $k$ is the number of possible meals ($1 \le k \le 100$).

Print on a single line the number of menus that avoid a rebellion, modulo $4\,000\,000\,009$. For $n = 0$ the only menu is the empty one, so the answer is $1$.

For $n = 3$, $\ell = 2$ and $k = 3$ there are exactly 12 menus with the required property.

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