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

Cerința

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

Date de intrare

Fișierul de intrare crescator.in conține o singură linie pe care se află numărul natural S.

Date de ieșire

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

Restricții și precizări

• 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

Exemplu:

crescator.in

4

crescator.out

11

Explicație

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