Cartel Bilingüe (2) P30660


Statement
 

pdf   zip

thehtml

Como sabréis, en Kazajistán se hablan dos lenguas: kazajo y ruso. Por eso típicamente los carteles están en ambos idiomas: primero en kazajo y a continuación en ruso. Además, a veces ponen todas las palabras juntas, una detrás de otra, sin ni siquiera separar entre los dos idiomas. Vuestra tarea es intentar descifrar uno de esos carteles.

Disponéis de un diccionario de kazajo y un diccionario de ruso, el primero con k palabras y el segundo con r palabras. (Aunque ambos idiomas se escriben en cirílico, nosotros usaremos una transliteración al alfabeto latino.) Como el kazajo y el ruso son lenguas totalmente diferentes, es posible que la traducción de uno a otro no tenga nada que ver, ni en número de palabras ni en longitud. Además, podría ser que el cartel estuviera en un solo idioma, ya sea kazajo o ruso. ¿De cuantas maneras posibles se podría descifrar el cartel?

Entrada

La entrada empieza con k, seguido de las k palabras kazajas, seguido de r, seguido de las r palabras rusas. Al final viene un cartel de longitud c. Ambos diccionarios tienen entre 1 y 20000 palabras. Tanto las palabras como el cartel contienen sólo letras minúsculas. La longitud de las palabras está entre 1 y 200, y c está entre 1 y 20000. No hay palabras repetidas dentro del mismo diccionario.

Salida

Escribid el número de formas de descifrar el cartel, módulo 109 + 7.

Puntuación

  • Test1:  ‍50 Puntos ‍

    Resolver entradas donde k y r son como mucho 1000, y c es como mucho 10.

  • Test2:  ‍20 Puntos ‍

    Resolver entradas donde c es como mucho 10.

  • Test3:  ‍30 Puntos ‍

    Resolver entradas de todo tipo.

Public test cases
  • Input

    2
    a
    aa
    2
    b
    bb
    aaaabbb
    

    Output

    15
    
  • Input

    1
    a
    2
    a
    aa
    aa
    

    Output

    4
    
  • Input

    4
    a
    aa
    aaa
    aaaa
    4
    a
    aa
    aaa
    aaaa
    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
    

    Output

    674769970
    
  • Input

    2
    abc
    a
    1
    cd
    abcd
    

    Output

    0
    
  • Information
    Author
    Lander Ramos
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++