Fork me on GitHub

teddy online judge

teddy es un oso de peluche

91. Contando Cuantos Ordenamientos

Limite de tiempo : 10 seg.   Total runs : 5  Aceptados : 2

Límite de tiempo Límite de memoria Archivo de entrada Archivo de salida
10s 64Mib data.in data.out

¡Buenas nuevas, todo mundo! Se ha encontrado la colonia de Limogochis más grande del mundo: han construido una torre hexagonal gigante donde cada vértice tiene una guarida con un Limogochi, y túneles que comunican las guaridas individuales de cada Limogochi. Cada guarida tiene un túnel que lo comunica con la guarida del mismo vértice del hexágono del piso inmediato superior y del piso inmediato inferior, además de el vértice inmediato a la izquierda, el vértice inmediato a la derecha y el vértice opuesto del hexágono. Aquí está un diagrama de uno de los pisos de la torre:

Diagrama del piso de la torre de Limogochis

Una de las cosas curiosas que encontraste es que cada Limogochi es vecino inmediato de su pareja (i.e. existe un túnel conectando su guarida con la de su pareja), entonces deciden compartir sus guaridas junto con el túnel que las conecta, para tener más espacio para vivir dignamente. Como buen limogochílogo del centro de Investigación de Todo lo Curioso (ITC), decides calcular cuántos acomodos distintos existen si hay 3·N parejas de Limogochis, llenando N pisos de la torre. Como en realidad a tí te interesa el acomodo de los túneles compartidos y no de los Limogochis en sí, realmente no importa qué Limogochi viva en qué guarida, simplemente cuáles tuneles están compartidos y cuáles no.

Uno de los 948 ordenamientos posibles para 9 parejas de Limogochis
Uno de los 948 ordenamientos posibles para 9 parejas de Limogochis

Entrada

La primer línea de la entrada contiene un entero Nc (1 ≤ Nc ≤ 100), que contiene el número de casos de prueba. Las siguientes Nc líneas contienen un único entero N (1 ≤ N ≤ 1018), que indica que hay que contar el número de acomodos posibles para 3·N parejas de Limogochis, llenando N pisos de la torre.

Salida

Para cada caso de prueba, imprime una línea con el número del caso, seguido del número de ordenamientos, módulo 1,000,000,007. Sigue el formato indicado en el ejemplo.

Entrada/Salida de ejemplo

5
1
2
3
4
1000000000000000000
Caso 1: 6
Caso 2: 82
Caso 3: 948
Caso 4: 11305
Caso 5: 471642603

Hecho por Alan Gonzalez @_alanboy ; Concepto Luis Hector Chavez @lhchavez ; Infraestructura por Instituto Tecnologico de Celaya

contribuciones de los usuarios bajo la licencia cc-wiki con atribucion requerida