Tu tarea consiste en contar el número de grillas diferentes de ~n x n~, cuyos cuadrados sean negros o blancos.

Dos grillas se consideran diferentes si no es posible rotar una de ellas para que se vean iguales.

Entrada

La única línea de entrada tiene un entero ~n~: el tamaño de la grilla.

Salida

Imprime un entero: el número de grillas módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 10^9~

Ejemplo de Entrada

4

Ejemplo de Salida

16456