Intercalación de palabras (2) P35236

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 $10^8 + 7$.