Tu tarea consiste en contar el número de formas en que los números ~1,2,\ldots,n~ pueden dividirse en dos conjuntos de igual suma.

Por ejemplo, si ~n=7~, hay cuatro soluciones:

{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~.

Salida

Imprime la respuesta módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 500~.

Ejemplo de Entrada

7

Ejemplo de Salida

4