Intercalació de paraules (2) P35236

Donades tres paraules $s$, $t$ i $u$ només amb lletres minúscules, digueu de quantes maneres es pot obtenir $u$ intercalant $s$ i $t$, sense modificar l’ordre relatiu ni entre les lletres de $s$, ni entre les de $t$.

Entrada

L’entrada consisteix en diversos casos, cadascun amb $s$, $t$ i $u$. Tant $s$ com $t$ tenen entre 1 i 1000 lletres minúscules. A més, $u$ té tantes lletres de cada com hi ha a $s$ i a $t$.

Sortida

Per a cada cas, escriviu el nombre d’intercalacions que produeixen $u$, mòdul $10^8 + 7$.