Camins P25900


Statement
 

pdf   zip

thehtml

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 ≠ y. Finalment, tenim el nombre e de vèrtexs especials, seguits d’aquests e vèrtexs en qualsevol ordre. Suposeu 2 ≤ n ≤ 104, 1 ≤ m ≤ 5n, 2 ≤ e ≤ 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 = 109 + 7.

Pista

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

Public test cases

  • Input

    2
1  0 1
2  0 1

3
3  1 2  2 0  1 0
3  2 0 1

3
2  0 1  0 2
2  1 2

    Output

    1
4
0
    • Information
    Author
    Javier López-Contreras
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++