| Fişierul intrare/ieşire: | dirichlet.in, dirichlet.out | Sursă | .com 2011 |
| Autor | Radu Stefan Voroneanu | Adăugată de |  Mr. Noname •cezar305 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dirichlet
Avem la dispozitie N bile si N cutii. Dorim sa impartim toate bilele in cutii astfel incat sa respecte urmatoarele conditii : prima cutie sa contina maxim o bila, primele 2 cutii sa contina maxim 2 bile, primele 3 cutii sa contina maxim 3 bile s.a.m.d. In cate moduri se poate realiza aceasta impartire?
Sa se afle numarul de moduri in care se poate realiza impartirea bilelor astfel incat sa se respecte conditiile. Deoarece numarul acestora poate fii destul de mare rezultatul se va calcula modulo 9999991.
Date de intrare
Fişierul de intrare dirichlet.in va contine numarul natural N reprezentand numarul de bile, respectiv de cutii.
Date de ieşire
În fişierul de ieşire dirichlet.out va contine un singur numar natural care reprezinta raspunsul cerintei.
Restricţii
- 1 ≤ N ≤ 1.000.000
- a modulo b reprezinta restul impartirii lui a la b
- Atentie! Se recomanda folosirea tipului long long pentru cei care implementeaza in C/C++ si int64 pentru cei care implementeaza in Pascal
Exemplu
| dirichlet.in | dirichlet.out |
|---|---|
| 3 | 5 |
Explicatii
pentru 3:
(*)(*)(*)
(*)()(**)
()(*)(**)
()(**)(*)
()()(***)
