MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

II Copa MATCOM ACM-ICPC

Ended

D - N-Reinas

Languages: C, C++, Java, Tiger, Python, Pascal, JavaScript, Haskell, C#
Time & Memory limits: (details)

En el juego del ajedrez la reina amenaza a piezas que se encuentren en su misma fila, columna o diagonal. El juego de las $N$ reinas consiste en colocar sobre un tablero de ajedrez de dimensiones $N \times N$, $N$ reinas sin que estas se amenacen entre ellas. Para este problema usted debe buscar la cantidad de distribuciones inválidas en lugar de las válidas, es decir, dado un entero $N$ usted debe encontrar todas las combinaciones de $N$ reinas sobre un tablero de ajedrez de $N \times N$ tal que existan al menos dos que se amenacen.

Input

Línea 1 : Un entero $N$ $(1 \le N \le 16)$.

Output

Línea 1 : Cantidad de distribuciones inválidas para el problema de las N-Reinas. Calcule el resultado módulo $10^9+7$.

Sample test(s)

Input
4
Output
1818

Hints

Hint

Una distribución inválida del problema 4-Reinas.