partitie

Se defineşte o partiţie a unui număr natural $n$ ca fiind o scriere a lui $n$ sub forma:

$n$ = $n_1$ + $n_2$ + $\dots$ + $n_k$, ($k \geq 1$), unde $n_1$, $n_2$, $\dots$, $n_k$ sunt numere naturale care verifică următoarea relaţie: $n_1 \geq n_2 \geq \dots \geq n_i \geq \dots \geq n_k \geq 1$.

Cerinţă:

Fiind dat un număr natural $n$, să se determine câte partiţii ale lui se pot scrie, conform cerinţelor de mai sus, ştiind că oricare număr $n_i$ dintr-o partiţie trebuie să fie un număr impar.

Date de intrare

Fişierul partitie.in conţine pe prima linie numărul $n$

Date de ieşire

Fişierul partitie.out va conţine pe prima linie numărul de partiţii ale lui $n$ conform cerinţelor problemei.

Restricții și precizări

• $1 \leq n \leq 160$;

Exemplu

partitie.in

7

partitie.out

5

Explicație

Cele cinci partiţii sunt:

• $1+1+1+1+1+1+1$;
• $1+1+1+1+3$;
• $1+1+5$;
• $1+3+3$;
• $7$;