Claudia vrea să construiască o scară cu N trepte astfel încât prima treaptă să fie la înălţimea 0 şi ultima treaptă să fie la înălţimea H. Fiind pusă pe glume, ea îi cere arhitectului să proiecteze o scară neobişnuită, în care treptele sunt dispuse astfel încât, la un moment dat, să poţi urca, coborî sau rămâne la acelaşi nivel. Pentru a fi uşor de urcat sau coborât, valoarea absolută a diferenţei dintre înălţimile la care se află oricare două trepte consecutive trebuie să fie mai mică sau egală cu o valoare dată, K. Nicio treaptă nu se poate afla la o înălţime negativă sau la o înălţime mai mare decât H.

Cerinţa

Scrieţi un program care să determine numărul de scări diferite cu N trepte, ce pot fi construite respectând cerinţele Claudiei. Deoarece numărul de scări poate fi foarte mare, determinaţi restul împărţirii acestui număr la 666013.

Date de intrare

Pe prima linie a fişierului scara.in se află numerele naturale N H K, separate prin câte un spaţiu, cu semnificaţia din enunţ.

Date de ieşire

Fişierul de ieşire scara.out va conţine pe prima linie o valoare care reprezintă numărul cerut.

Restricţii şi precizări

• 1 ≤ N ≤ 109
• 1 ≤ H ≤ 100
• 1 ≤ K ≤ H
• Pentru un număr de teste în valoare de 30 de puncte, N ≤ 20.000 şi H ≤ 20
• Pentru un număr de teste în valoare de 50 de puncte, N ≤ 500.000 şi H ≤ 30
• Pentru un număr de teste în valoare de 80 de puncte, H ≤ 30

Exemplu:

scara.in

4 3 2

scara.out

8

Explicație

0 0 1 3
0 2 3 3
0 1 2 3
0 1 3 3
0 2 1 3
0 0 2 3
0 1 1 3
0 2 2 3