Crescator2

crescator2

== include(page="template/taskheader" task_id="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ă.

Poveste şi cerinţă...

h2. Date de intrare

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

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

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

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

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

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

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

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