Florin este iar în Drobeta-Turnu Severin. Din păcate nu a scăpat de hoții de buzunare care îi cauzează atâtea probleme! Aceștia l-au urmărit chiar și aici! Cu toate acestea, el a aflat cum poate sa scape de ei. Drobeta-Turnu Severin este un oraș sub forma de un graf orientat aciclic cu n noduri și m muchii. Pentru ca hoții să îi piardă urma, Florin (care se află în nodul 1) trebuie să ajungă în nodul n pe un anumit traseu. El a reușit să obțină o listă A cu p noduri. În drumul său de la 1 la n el trebuie sa parcurgă aceste p noduri în ordinea în care sunt date, altfel acesta nu va scăpa de hoți!

Cerința

Aflați numărul de trasee posibile de la 1 la n astfel încât să se treacă prin cele p noduri în ordinea în care sunt date. Pentru că rezultatul poate fi foarte mare, se va afișa restul împărțirii acestuia la 1.000.000.007.

Date de intrare

Prima linie se vor citi de la tastatura trei numere naturale n, m și p. Pe a doua linie se vor afla p numere, reprezentând nodurile ce trebuie parcurse de Florin în ordinea în care sunt date. Pe următoarele m linii se vor afla muchiile din graf reprezentate prin câte două numere naturale x și y, cu semnificația că există muchie de la x la y.

Date de ieșire

Pe prima linie va fi afișat pe ecran un singur număr natural reprezentând numărul de astfel de trasee modulo 1.000.000.007.

Restricții și precizări

• m, n, p ≤ 1.000.000
• ATENȚIE! Pot exista mai multe muchii intre aceleași două noduri!
• Rezultatul se va afișa modulo 1.000.000.007
• Florin ar rezolva singur problema, dar sta atât de mult prin restaurante, încât nu mai are timp nici sa facă palate!
• Problema se numește “scoică” din motive necunoscute lui Sorin.

Exemplu:

Intrare

6 9 3
3 5 6
1 3
1 3
1 2
2 3
2 4
3 4
3 5
4 5
5 6

Ieșire

6

Explicație

Cele 6 drumuri sunt:
1-3-5-6
1-3-4-5-6
1-3-5-6
1-3-4-5-6
1-2-3-5-6
1-2-3-4-5-6
Se observă că 1-3-5-6 apare de doua ori, dar aceasta este datorata faptului că sunt două muchii între 1 și 3. Unul din drumuri folosește una dintre muchii, pe când celălalt folosește cealaltă muchie. Aceeași situație apare și la drumul 1-3-4-5-6.