Shell
시간 제한1초메모리 제한512 MB
DAG에서 정점 1에서 n으로 가는 경로 중 주어진 p개 정점을 순서대로 지나는 경로의 수를 1e9+7로 나눈 나머지로 구한다. 중복 간선은 각각 다른 경로로 센다.
문제
Florin은 다시 Drobeta-Turnu Severin에 왔다. 안타깝게도 그를 괴롭히는 소매치기들을 아직 떨쳐내지 못했다. 그들은 이 아름다운 도시까지 Florin을 따라왔다. 하지만 Florin은 매우 영리해서 그들을 떨쳐내는 방법을 알아냈다. Drobeta-Turnu Severin은 n개의 정점과 m개의 간선을 가진 방향성 비순환 그래프로 나타낼 수 있는 도시다. 그 성가신 소매치기들을 완전히 떨쳐내려면, 처음에 정점 1에 있는 Florin이 특정 경로를 따라 정점 n에 도달해야 한다. 그는 p개의 정점 목록을 확보했다. 정점 1에서 정점 n으로 가는 길에 그는 이 p개의 정점을 모두 주어진 순서대로 지나야 하며, 그렇지 않으면 소매치기들을 떨쳐내지 못하고 우리의 영웅은 매우 속상해질 것이다.
정점 1에서 정점 n으로 가면서 목록의 p개 정점을 모두 주어진 순서대로 지나는 경로의 수를 구하라. 결과가 매우 클 수 있으므로 답을 1,000,000,007로 나눈 나머지로 출력하라.
입력
첫 번째 줄에 세 정수 n, m, p가 주어진다.
두 번째 줄에 Florin이 주어진 순서대로 지나야 하는 p개의 정점이 주어진다.
다음 m개의 줄에 그래프의 간선이 두 정수 x, y로 주어지며, 이는 정점 x에서 정점 y로 가는 간선이 있음을 뜻한다.
출력
첫 번째 줄에 경로의 수를 1,000,000,007로 나눈 나머지를 나타내는 정수 하나를 출력한다.
제한
- 같은 두 정점 사이에 간선이 여러 개 있을 수 있다.
- n, m, p ≤ 1,000,000
힌트
6개의 경로는 다음과 같다.
- 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
1-3-4-5-6이 2번 나타나는 것은 1에서 3으로 가는 간선이 2개이기 때문이다. 한 경로는 한 간선을 사용하고, 다른 경로는 다른 간선을 사용한다. 1-3-5-6도 마찬가지다.