teddy online judge |
|
|
teddy es un oso de peluche |
Datos invalidos
91. Contando Cuantos Ordenamientos
Limite de tiempo : 10 seg. Total runs : 7 Aceptados : 3
| 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:
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
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 |