En el puerto de La Habana, un grupo de estibadores organiza una serie de contenedores numerados del ~1~ al ~N~ para ser cargados en un enorme buque de carga.

Sin embargo, durante el registro, todos los números fueron escritos sin espacios entre ellos, formando una sola cadena de dígitos.

El capitán, un hombre supersticioso, solo permitirá que el barco zarpe si la secuencia resultante es divisible por ~11~, número que considera de buena fortuna en el mar.

Tu tarea es ayudar a los trabajadores a determinar cuántas permutaciones de los números del ~1~ al ~N~ forman una secuencia concatenada que, al interpretarse como un número entero, sea divisible por ~11~.

Como el resultado puede ser muy grande, imprime la respuesta módulo ~10^9 + 7~.

Entrada

La primera línea contiene un número entero ~N~ (~1 \le N \le 99~): la cantidad de números disponibles para la secuencia.

Salida

Imprime un único número: la cantidad de permutaciones de los números del ~1~ al ~N~ que forman una secuencia divisible por ~11~, módulo ~10^9 + 7~.

Subtareas

Subtarea	Condición adicional	Puntos	Dependencia
1	~N \le 9~	10	Ninguna
2	~N \le 13~	10	Debe pasar la subtarea 1
3	~N \le 16~	15	Debe pasar la subtarea 2
4	~N \le 24~	15	Debe pasar la subtarea 3
5	Sin restricciones adicionales	50	Debe pasar la subtarea 4

Ejemplos

Entrada 1

3

Salida 1

2

Explicación

Las posibles permutaciones son: ~123, 132, 213, 231, 312, 321~. Entre ellas, ~132~ y ~231~ son divisibles por ~11~. Por lo tanto, la respuesta es ~2~.

Entrada 2

10

Salida 2

331200