Sečenje

Dat je štap dužine \(n\) metara. Potrebno je preseći ga na nekoliko mesta tako da dobijeni delovi budu celobrojne dužine i nijedan od dobijenih delova ne bude duži od \(k\) metara. Napisati program koji određuje na koliko načina je moguće izvršiti ovakvo sečenje.

Opis ulaza

Sa standardnog ulaza se unose brojevi \(n\) (\(1 \leq n \leq 1000\)) i \(k\) (\(1 \leq k \leq 300\)).

Opis izlaza

Na standardni izlaz ispisati broj mogućih sečenja. Kako taj broj može biti velik, ispisati njegov ostatak pri deljenju sa \(10^9 + 9\).

Primer

Ulaz

4 2

Izlaz

5

Objašnjenje

Objašnjenje

Moguća su sledeća sečenja predstavljena dužinama dobijenih delova štapa:

1 1 1 1
2 1 1
1 2 1
1 1 2
2 2