10961번 - School canteen 다국어

Once upon a time, there was a school canteen. And the cooks were very busy there. They had to prepare a menu for all n days of the school year, but they had to admit that they are able to make only k different meals.

Alas, the students are known to be picky eaters. (Which is a well established Czech tradition.) If they get the same meal for ℓ days consecutively, they rebel against the cooks. (defenestration, which is another fine Czech tradition.)

Count the number of menus, which avoid student rebellion.

On the standard input, you will find a single line containing three space-separated integers: n, ℓ, and k. Here n is the number of days (0 ≤ n ≤ 2,000,000,000), ℓ the impatience of the students (the number of repeats of a single meal, which causes the students to rebel, 2 ≤ ℓ ≤ 200), and k is the number of possible meals (1 ≤ k ≤ 100).

The standard output shall contain a single integer: the number of possible menus modulo 4,000,000,009.

There are exactly 12 menus of the required properties:

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