Intercalación de palabras (2) P35236


Statement
 

pdf   zip

thehtml

Dadas tres palabras s, t y u sólo con letras minúsculas, decid de cuantas maneras se puede obtener u intercalando s y t, sin modificar el orden relativo ni entre las letras de s, ni entre las de t.

Entrada

La entrada consiste en diversos casos, cada uno con s, t y u. Tanto s como t tienen entre 1 y ‍1000 letras minúsculas. Además, u tiene tantas letras de cada como hay en s y en t.

Salida

Para cada caso, escribid el número de intercalaciones que producen u, módulo 108 + 7.

Public test cases
  • Input

    abcd xyz xabycdz
    abcd xyz xabydcz
    a b ba
    z z zz
    abba ba babbaa
    ab ab baab
    irr i irir
    ssss ssss ssssssss
    aaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa
    aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
    

    Output

    1
    0
    1
    2
    2
    0
    1
    70
    540174
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++