Camins alternats en un graf P80164

Considereu un graf dirigit sense cicles on cada vèrtex està etiquetat amb una lletra. Donat un natural ℓ, podeu calcular quants camins amb ℓ 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 ℓ 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 ≠ y. Suposeu 2 ≤ n ≤ 1000, 1 ≤ m ≤ 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 ℓ 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⁸ + 7.

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