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 $\Theta(\vert s \vert \cdot \vert t \vert)$, 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^8 + 7$.