crescator2

Crescator2

== include(page="template/taskheader" task_id="crescator2") ==

Poveste şi cerinţă...

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ă.

h2. Date de intrare

Fişierul de intrare $crescator2.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $crescator2.out$ ...

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*}.

h2. Restricţii

* $... ≤ ... ≤ ...$

* 1 ≤ {*S*} ≤ 50.000
* Un şir de numere a{~1~} a{~2~} a{~3~}...a{~n~} este crescător dacă a{~1~} ≤ a{~2~} ≤ a{~3~} ≤... ≤ a{~n~}
* Pentru 20% din teste {*S*} ≤ 50
* Pentru 40% din teste {*S*} ≤ 400
* Pentru 60% din teste {*S*} ≤ 6000

h2. Exemplu

table(example). |_. crescator2.in |_. crescator2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. crescator2.in |_. crescator2.out |_. Explicaţ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
|

== include(page="template/taskfooter" task_id="crescator2") ==
 

== include(page="template/taskfooter" task_id="crescator2") ==