Cerința

Se citește un număr natural n (n<31). Determinați în câte moduri se poate partiționa mulțimea {1,2,…,n} în două submulțimi disjuncte A și B astfel încât suma elementelor din submulțimea A să fie egală cu suma elementelor din submulțimea B.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran numărul de partiționări confirm cerinței.

Restricții și precizări

• 1 < n < 31
• O partiționare de forma {1,2,4,7} U {3,5,6} este identică cu {3,5,6} U {1,2,4,7} și se număra doar una dintre ele.
• Dacă mulțimea nu se poate partiționa conform cerinței, atunci se va afișa 0. De exemplu, mulțimea {1,2,3,4,5} nu poate fi partiționată conform cerinței.

Exemplu:

Intrare

7

Ieșire

4

Explicație

Cele 4 moduri de a partiționa mulțimea {1,2,3,4,5,6,7} în două submulțimi cu sume egale sunt: {1,2,4,7} U {3,5,6}, {1,2,5,6} U {3,4,7} , {1,3,4,6} U {2,5,7} și {1,6,7} U {2,3,4,5}.