Cerința

Se consideră un șir format din primele N numere naturale nenule. Să se afle numărul de partiții în 2 submulțimi disjuncte cu suma egală care există pentru acest șir.

Date de intrare

Programul citește de la tastatură numărul N.

Date de ieșire

Programul va afișa pe ecran numărul cerut, modulo 2^32.

Restricții și precizări

• 1 ≤ N ≤ 2000
• {a, b} == {b, a}
• {a, b} U {c} != {c} U {a, b}

Exemplu 1:

Intrare

2

Ieșire

0

Explicație

Se consideră șirul [1, 2]. După cum se poate observa, nu se poate partiționa în 2 submulțimi disjuncte cu suma egală.

Exemplu 2:

Intrare

7

Ieșire

8

Explicație

Se consideră șirul [1, 2, 3, 4, 5, 6, 7]. Aici sunt modalitățile de a-l partiționa în 2 submulțimi disjuncte cu suma egală:

{2, 3, 4, 5} U {1, 6, 7}
{1, 6, 7} U {2, 3, 4, 5}
{1, 3, 4, 6} U {2, 5, 7}
{2, 5, 7} U {1, 3, 4, 6}
{1, 2, 4, 7} U {3, 5, 6}
{3, 5, 6} U {1, 2, 4, 7}
{1, 2, 5, 6} U {3, 4, 7}
{3, 4, 7} U {1, 2, 5, 6}