Fişierul intrare/ieşire:crescator2.in, crescator2.outSursăUrmasii lui Moisil 2016, Clasele 11-12
AutorTudose Vlad AndreiAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test0.8 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Crescator2

Aurel a învăţat la matematică despre şiruri de numere. Fiind curios din fire, el ar vrea acum să ştie câte şiruri crescătoare de numere naturale nenule cu suma elementelor mai mică sau egală cu S există.

Ajutaţi-l pe Aurel să afle câte astfel de şiruri există.

Date de intrare

Fişierul de intrare crescator2.in conţine o singură linie pe care se află numărul natural S.

Date de ieşire

Fişierul de ieşire crescator2.out va conţine o singură linie pe care se va scrie numărul de şiruri dorit de Aurel, calculat modulo 700001.

Restricţii

  • 1 ≤ S ≤ 50.000
  • Un şir de numere a1 a2 a3...an este crescător dacă a1 ≤ a2 ≤ a3 ≤... ≤ an
  • Pentru 20% din teste S ≤ 50
  • Pentru 40% din teste S ≤ 400
  • Pentru 60% din teste S ≤ 6000

Exemplu

crescator2.increscator2.outExplicaţie
4
11
Cele 11 şiruri sunt:
1
1 1
1 1 1
1 1 1 1
1 1 2
1 2
1 3
2
2 2
3
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?