Due insiemi con la stessa somma
Dato un intero positivo
n, determina in quanti modi si possano dividere i numeri 1, 2, ..., n in due insiemi la cui somma sia uguale.
Per esempio, se
n = 7, esistono quattro modi per suddividere i numeri in due insiemi con la stessa somma
{1, 3, 4, 6} e {2, 5, 7}
{1, 2, 5, 6} e {3, 4, 7}
{1, 2, 4, 7} e {3, 5, 6}
{1, 6, 7} e {2, 3, 4, 5}Input
L’unica riga di input contiene un intero
n (1 ≤ n ≤ 500).Output
Stampa la risposta modulo .
Esempi
Input | Output |
7 | 4 |
10 | 0 |
Constraints
Time limit: 20 seconds
Memory limit: 512 MB
Output limit: 1 MB