Pracsiu Dan (dnprx) N un număr natural. Definim o partiție pe două linii a numărului N ca fiind două șiruri nevide de numere naturale a1, a2, …, ak și b1, b2, …, bp (k ≥ p), cu proprietățile:
a1> a2> ... > ap> ... > akb1> b2> ... > bpb1≤ a1,b2≤ a2, …,bp≤ apa1+ a2+ ... + ak+ b1+ b2+... + bp= N
Exemplu : Cele 7 partiții pe două linii ale numărului N = 6 sunt:
5 4 3 3 2 3 1 4 1 2 1
1 ; 2 ; 3 ; 1 ; 2 ; 1 ; 2 1
Cerința
Să se scrie un program care citește numărul natural N și determină numărul P de partiții pe două linii ale numărului natural N.
Date de intrare
Fișierul de intrare pdl.in conţine pe prima linie numărul natural N.
Date de ieșire
Fișierul de ieșire pdl.out va conţine pe prima linie restul împărțirii numărul P la 3000017.
Restricții și precizări
1 ≤ N ≤ 2000- un șir de numere este nevid dacă conține cel puțin un element
Exemplu:
pdl.in
6
pdl.out
7
Explicație
N = 6. Sunt 7 partiții pe două linii conform exemplului de mai sus.