In-order#11757
La ceremonia de apertura de los Juegos Olímpicos tendrá lugar en el río con equipos en barcos. La disposición de los atletas en la parte superior del barco se ha diseñado de una manera muy específica: para cada equipo, los atletas (convenientemente numerados del al ) están organizados como un árbol binario.
El organizador también ha diseñado el recorrido en pre-orden, el recorrido en post-orden y una parte consecutiva (posiblemente vacía) del recorrido en in-orden del árbol binario que cada equipo debe seguir.
Ahora, para asegurarse de que haya suficientes disposiciones de árboles para que cada equipo pueda tener una distinta, se te pide calcular la cantidad de posibles recorridos en in-orden diferentes, digamos , módulo el número primo .
Consiste en cuatro líneas. La primera línea contiene el número . Cada línea subsiguiente contiene una lista de enteros.
La segunda línea contiene una lista a_1, a_2, ..., a_n, donde a_k es el número del -ésimo atleta encontrado en el recorrido en pre-orden.
La tercera línea contiene una lista b_1, b_2, ..., b_n, donde b_k es el número del -ésimo atleta encontrado en el recorrido en post-orden.
La cuarta línea contiene una lista c_1, c_2, ..., c_n, donde c_k es el número del -ésimo atleta encontrado en el recorrido en in-orden, o si el organizador no indicó quién debería ser ese -ésimo atleta.
Imprime un entero : este es el único entero tal que 0 \le s < 999\ 999\ 937 y para el cual t − s es divisible por .
Ejemplo 1
Ejemplo 2
Ejemplo 3