ultima problemă
grupă: micăsursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
nkbiti
Timp maxim de execuţie/test:
2.7
secunde
Memorie totala disponibilă/stivă:
16
MB/1 MB
Gigel a devenit în ultima vreme pasionat de biţi. El se gândeşte serios (tipic Gigel) la următoarea problemă: Câte şiruri de N biţi cu maximum K biţi de 0 consecutivi există?
Cerinţă
Să se determine răspunsul la întrebarea lui Gigel.
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 Gigel. Deoarece acest răspuns poate fi foarte mare Gigel vă roagă sa afişaţi răspunsul modulo 666777 .
Restricţii
1 ≤ N ≤ 200 000 000 (2 * 108 )
1 ≤ K ≤ 40
Pentru 40% din teste N ≤ 100 000
Exemple
nkbiti.in nkbiti.out
4 2 13
Probleme recomandate
De la .campion 2009 : efort , muzeu , bal , seti , basm , dansatori , smith , timer , secvsir , vot , cetati , reziduu , biliard , prefix1 , accesibil , dp , jocv , placa , palc , prod3 , predecesor , standard , cantor , nori , triti , kperms , sotron1 , impozit , tablite , fazan , lanturi , secvpar , tom , joker , matriosca , asociativ , lego , medalii , permutari , cfr , treegame , scanduri , site , fotbal , links , kbiti , segm , album , iepurasi , jucarii , m4 , bradut , trmv , colorare , greutati , concat , graphgame , ic , echilibru , brazi , mat , cubinvers , mobil , distsir , parbit De acelaşi autor : votare , kperms , site , kbiti , kdist , oldest , mess , subs , subsiruri Despre programare dinamică : vedete , fbr , tgv , zeratul , rv , comun , retea , circuit , sumdif , copaci , drum , text , palind , joc , vikingi , rafturi , balaur , plimbare , party , pc , pioni , seif , iepuri , numere3 , perm , ture , bilete , prop , ro , reduceri , cuburi , invest , cutie2 , stalpi , nr2 , judete , strict , auto2 , tree , jobs , leaves , pstring , program , datorii , senzori , farfurii , joc1 , barbie , ambigram , rlcs , cub1 , bio , chimie1 , otilia , pasune , remi , sir23 , tren1 , joc5 , pachete , echipe , comb , agitatie , ivv , peste , pitici , pipe , shgraf , tabara1 , stop , randuri , zidar , log , sant , produs , subsir , cover , bcast , emax , dist , mesaj1 , imax , avere , asmax , raft , suma2 , joc12 , fni , nr4 , join , transport , masina3 , lsort , microvirus , fat , cafea , echipe1 , anticip , bsir , diamant , petrom , evantai , spion , acolor , evo , bombo , lacusta , lant , team , pitici1 , numere8 , dep , stiva , subgeom , pviz , tir1 , cabane , piramida1 , mosia , cuvinte1 , gaina , materom , sortari , turnuri , trans , politie , codul , dansatori , kperms , treegame , siruri2 , 123 , jucarii , bradut , joc15 , expozitie , text3 , ic , echilibru , distsir , kmax , stalpi1 , gaz , triunghi2 , v2d , cuiburi , mine , orientare , activ , secvbiti , kcons , pokemon , ubergraf , left , acerc , autostrazi , kdist , select , cazare , fluviu , telecomanda , parcela , pion , subs , suma4 , sirmax , bdotcom , viena , sablon2 , telecab , ikebana , radare , hacker , obstacole , robotel , centrala , verigi , cds , wg , minusk , radioactiv , enigma , jb , efect , maxviz , ripstick , progresii , maxtri , combcuv , blis , subsiruri , mijloc , probleme , unuzero , palindrom1 , minerale , speed , zmax , spider , cntgcd , interclasare , bus , pariuri , riglef , fractii2 , fall , arbsum , conuri , arbvalmax , procente , metrou