Dois Conjuntos Iguais
Dado um inteiro positivo
n, determine quantas maneiras existem de separar os números 1, 2, ..., n em dois conjuntos com a mesma soma.
Por exemplo, se
n = 7, existem quatro maneiras de dividir os números em dois conjuntos com soma igual
{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}Entrada
A única linha de entrada contém um inteiro
n (1 ≤ n ≤ 500).Saída
Imprima a resposta considerando o resultado módulo .
Exemplos
Entrada | Saída |
7 | 4 |
10 | 0 |
Constraints
Time limit: 20 seconds
Memory limit: 512 MB
Output limit: 1 MB