Fişierul intrare/ieşire:nkbiti.in, nkbiti.outSursă.campion 2009 runda 2
AutorMircea DimaAdăugată deblasterzMircea Dima blasterz
Timp execuţie pe test0.45 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Nkbiti

Boolanel a devenit în ultima vreme pasionat de biţi. El se gândeşte serios (tipic Boolanel) la următoarea problemă: Câte şiruri de N biţi cu maximum K biţi de 0 consecutivi există?

Să se determine răspunsul la întrebarea lui Boolanel.

Date de intrare

Fişierul de intrare nkbiti.in va conţine o singură linie pe care se afla două numere naturale N şi K separate printr-un spaţiu.

Date de ieşire

Fişierul de ieşire nkbiti.out va conţine o singură linie cu răspunsul dorit de Boolanel. Deoarece acest răspuns poate fi foarte mare Boolanel vă roagă sa afişaţi răspunsul modulo 666777.

Restricţii

  • 1 ≤ N ≤ 1 000 000 000
  • 1 ≤ K ≤ 40
  • Pentru 40% din teste N ≤ 100 000
  • Pentru 60% din teste N ≤ 6 000 000

Exemplu

nkbiti.innkbiti.out
4 2
13
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content