Zwei gleich große Summen
Gegeben ist eine positive ganze Zahl
n. Bestimmen Sie, auf wie viele Arten sich die Zahlen 1, 2, ..., n in zwei Mengen mit derselben Summe aufteilen lassen.
Beispielsweise gibt es für
n = 7 vier Möglichkeiten, die Zahlen in zwei Mengen mit gleicher Summe zu unterteilen:
{1, 3, 4, 6} und {2, 5, 7}
{1, 2, 5, 6} und {3, 4, 7}
{1, 2, 4, 7} und {3, 5, 6}
{1, 6, 7} und {2, 3, 4, 5}Eingabe
Die einzige Eingabezeile enthält eine ganze Zahl
n (1 ≤ n ≤ 500).Ausgabe
Geben Sie die Antwort modulo aus.
Beispiele
Eingabe | Ausgabe |
7 | 4 |
10 | 0 |
Constraints
Time limit: 20 seconds
Memory limit: 512 MB
Output limit: 1 MB