Dos Conjuntos Iguales
Dado un número entero positivo
n, se debe contar cuántas formas hay de repartir los números 1, 2, ..., n en dos conjuntos de suma igual.
Por ejemplo, si
n = 7, hay cuatro maneras de dividir los números en dos conjuntos con la misma suma
{1, 3, 4, 6} y {2, 5, 7}
{1, 2, 5, 6} y {3, 4, 7}
{1, 2, 4, 7} y {3, 5, 6}
{1, 6, 7} y {2, 3, 4, 5}Entrada
La única línea de entrada contiene un número entero
n (1 ≤ n ≤ 500).Salida
Imprime la respuesta módulo .
Ejemplos
Entrada | Salida |
7 | 4 |
10 | 0 |
Constraints
Time limit: 20 seconds
Memory limit: 512 MB
Output limit: 1 MB