시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

문제

Florin is again in Drobeta-Turnu Severin. Unfortunately, he did not get rid off the pickpockets that bother him so much! They followed him even in this beautiful city! But Florin is very smart and figured out how to get rid of them. Drobeta-Turnu Severin is a city that is represented by a directed acyclic graph with n vertices and m edges. To finally get rid of those annoying pickpockets, Florin(who is initially in vertex 1) has to reach vertex n using a certain path. He managed to obtain a list of p vertices. In his way from vertex 1 to vertex n he has to cross all these p nodes in the given order, or else he will not get rid of the pickpockets and our hero will be very upset.

Find the number of possible paths from vertex 1 to vertex n that cross all p vertices in the given order from the list. Because the result can be very big you have to print the answer modulo 1,000,000,007.

입력

The first line contains three integers n, m and p.

The second line contains the p vertices that have to be crossed by Florin in the given order

The next m lines contain the edges from the graph, represented by two integers x and y, meaning there is an edge from vertex x to vertex y.

출력

The first line will contain only one integer representing the number of paths modulo 1,000,000,007.

제한

  • There can be more edges between the same 2 vertices.
  • n, m, p ≤ 1,000,000

예제 입력 1

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

예제 출력 1

6

힌트

The 6 paths are:

  • 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

It can be observed that 1-3-4-5-6 appears 2 times, this is because there are 2 edges from 1 to 3. One of the paths use an edge, the second one uses the other edge. The same situation is for 1-3-5-6.