Intercalant paraules P34319

Donades dues paraules s i t, de quantes maneres es poden intercalar tots els seus caràcters respectant l’ordre relatiu dins de cada paraula, i de manera que al resultat final no hi hagi dos caràcters consecutius iguals?

Per exemple, s= “a” i t= “bc” es poden intercalar de tres maneres: “abc”, “bac” i “bca”. Com un altre exemple, s= “ab” i t= “ab” només poden produir “abab”, però de dues maneres diferents (posant abans s, o posant abans t), així que aquí el resultat és 2.

Entrada

L’entrada consisteix en diversos casos, cadascun amb s i t. Podeu suposar que les longituds d’ambdues paraules estan entre 1 i 500. També podeu suposar que les paraules només estan formades per lletres minúscules, encara que la solució esperada, que té cost Θ(| s | · | t |), no ‍fa servir aquest fet.

Sortida

Per a cada cas, escriviu el nombre d’intercalacions possibles. Com que el resultat pot ser molt gran, feu els càlculs mòdul 10⁸ + 7.