Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: skaiciaus_skaidymas2.in

Rezultatų failas: skaiciaus_skaidymas2.out

Jei norite pateikti savo sprendimą - prisijunkite.

Skaičiaus skaidymas 2

Skaičių 5 galima užrašyti kaip kitų skaičių sumą:

5 = 5
5 = 1 + 4
5 = 2 + 3
5 = 1 + 1 + 3
5 = 1 + 2 + 2
5 = 1 + 1 + 1 + 2
5 = 1 + 1 + 1 + 1 + 1

Iš šių būdų 2 yra sudaryti iš 3 narių (1+1+3 ir 1+2+2). Iš šių vienas būdas sudaro super didėjančią seką, t.y. kiekvienas elementas yra nemažesnis nei prieš jį buvusių elementų suma (0\\leq1, 0+1\\leq1, 0+1+1\\leq3). Jums reikės rasti keliais būdais galima užrašyti skaičių 1\\leqn\\leq1000000, kai sudėtyje privalo būti 1\\leqk\\leq20 narių, sudarančių super didėjančią seką.

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje bus pateikti skaičiai n ir k.

Išvestis

Vienintelis skaičius - galimų sumų kiekis moduliu 10^9+9.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5 3
 
1
 
7 3
 
2
 
1 2
 
0