Camins alternats en un graf P80164

Considereu un graf dirigit sense cicles on cada vèrtex està etiquetat amb una lletra. Donat un natural $\ell$, podeu calcular quants camins amb $\ell$ vèrtexs conté el graf, tals que la paraula formada pel camí comença en consonant, i alterna consonants i vocals?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs $n$, el nombre d’arcs $m$, i un natural $\ell$ entre 1 i $n$. Segueix una paraula amb $n$ lletres minúscules, corresponents respectivament als vèrtexs 0, …, $n-1$. Segueixen $m$ parells $x$ $y$ indicant un arc des d’$x$ fins a $y$, amb $x \ne y$. Suposeu $2 \le n \le 1000$, $1 \le m \le 5n$, que els vèrtexs es numeren des de zero, que no hi ha arcs repetits, i que el graf no té cicles.

Sortida

Per a cada cas, escriviu el nombre de camins amb $\ell$ vèrtexs tals que la primera lletra és consonant, la segona és vocal, etc. Considereu, com és habitual, que les úniques vocals són ‘a’, ‘e’, ‘i’, ‘o’ i ‘u’. Com que la resposta pot ser molt grossa, feu els càlculs mòdul $10^8 + 7$.

Com a mostra, les quatre paraules corresponents al primer cas de l’exemple d’entrada són “bar”, “bad”, “bed” i “red”.