Dragon's Lair
En 1983, Don Bluth, exanimador de Disney, publicó el videojuego Dragon's Lair para laserdisc. En aquella época el hardware de los ordenadores y videoconsolas era muy limitado. El laserdisc, un antiguo soporte para películas, permitió hacer uso de vídeo de movimiento completo. El juego estaba troceado en infinidad de pequeñas secuencias de animación pregrabada, con un estilo y calidad que recordaba a las películas de Disney de la época. El jugador podía elegir cada pocos segundos las acciones del protagonista, para que tomara un camino u otro, o atacara o no a los enemigos. En función de las decisiones tomadas, se saltaba a una sección distinta, haciendo evolucionar la historia.
Hoy se conoce a este género de videojuegos como películas interactivas y la idea ha ido olvidándose y volviendo a surgir varias veces a lo largo de las décadas. Crearlas supone construir un guion que se ramifica y, en función de él, crear pequeñas secciones de vídeos que, unidos, hacen que el espectador pueda ver la película que él mismo construye. En función del guion, puede haber distintas formas de llegar a un mismo punto intermedio y acabar en múltiples finales, algunos favorables y otros negativos.
Entrada
Cada caso de prueba comienza con un número n entre 2 y 5.000 indicando en cuántas secuencias se encuentra dividido el guion de una película interactiva. A continuación aparecen n líneas describiendo cada una de ellas, por orden.
Una secuencia se describe comenzando con un número e que indica entre cuántas opciones se puede elegir el siguiente paso. A continuación aparecen e números distintos entre 1 y n con el índice de la secuencia a la que la película salta por cada opción. En total no habrá nunca más de 50.000 opciones.
Las secuencias que se corresponden con un final de la película no ofrecen opciones. En ese caso, tras el 0 que indica que el jugador no puede elegir el siguiente paso, aparece el texto FELIZ o AMARGO para indicar si en ese punto la película interactiva acaba o no de forma feliz para el espectador.
La primera secuencia descrita, la 1, es el punto de inicio de la película. Se garantiza que todas las secciones son alcanzables desde ese inicio. Además, aunque puede haber varias formas de llegar a la misma secuencia del guion, la película siempre avanza. Se garantiza que no hay ciclos que hagan que el espectador pueda volver una y otra vez a la misma secuencia.
Salida
Por cada caso de prueba el programa escribirá cuántas visualizaciones completas distintas pueden conseguirse con el guion de la película interactiva indicada, proporcionando primero cuántas terminan en un final feliz y luego cuántas lo hacen en un final amargo. Como los números pueden ser muy altos se proporcionará el resto de dividir cada uno por 1.000.000.007.
Entrada de ejemplo
3 2 2 3 0 FELIZ 0 AMARGO 5 2 4 5 0 FELIZ 0 AMARGO 2 2 3 1 3
Salida de ejemplo
1 1 1 2