pdl

Fie $N$ un număr natural. Definim o partiție pe două linii a numărului $N$ ca fiind două șiruri nevide de numere naturale $a_1, a_2, \dots, a_k$ și $b_1, b_2, \dots, b_p$ ($k \geq p$), cu proprietățile:

• $a_1 > a_2 > \dots > a_p > \dots > a_k$
• $b_1 > b_2 > \dots > b_p$
• $b_1 \leq a_1$, $b_2 \leq a_2$, $\dots$, $b_p \leq a_p$
• $a_1 + a_2 + \dots + a_k + b_1 + b_2 + \dots + b_p = N$

Exemplu:

Cele $7$ partiții pe două linii ale numărului $N = 6$ sunt:

Cerinţă

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 $3 \ 000 \ 017$.

Restricţii şi precizări

• $1 \leq N \leq 2 \ 000$
• 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.