Camins P25900

Considereu un graf dirigit sense cicles, amb alguns vèrtexs especials. Podeu comptar el nombre de camins que comencen en un vèrtex especial i acaben en un altre vèrtex especial?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs $n$ i el nombre d’arcs $m$. Segueixen $m$ parells $x$ $y$ indicant un arc des d’$x$ fins a $y$, amb $x \ne y$. Finalment, tenim el nombre $e$ de vèrtexs especials, seguits d’aquests $e$ vèrtexs en qualsevol ordre. Suposeu $2 \le n \le 10^4$, $1 \le m \le 5n$, $2 \le e \le n$, que els vèrtexs es numeren a partir de 0, i que no hi ha més d’un arc des d’un vèrtex fins a un altre.

Sortida

Per a cada cas, escriviu quants camins comencen en un vèrtex especial i acaben en un altre vèrtex especial. Com que el resultat pot ser molt gros, feu els càlculs mòdul $MOD = 10^9 + 7$.

Pista

Segons com sigui la vostra solució, tinguen cura si feu una resta mòdul $MOD$.