1649번 - 택시

문제

서울에서 민승이는 택시운전을 하고 있다. 서울은 1부터 N번까지 숫자로 붙여진 N개의 교차로로 구성되어있다. 그리고 어떤 교차로들은 도로로 연결되어 있는데 이 도로는 너무 좁아서 일방통행만이 가능하다. 민승이는 오랜 택시 경험상 어떤 교차로에서 출발해서 다시 그 교차로로 돌아올 수 없고, 어떠한 교차로 사이에도 두 개 이상의 도로가 없다는 것을 알고 있다.

어느 날 교차로 A에서 민승이는 한 명의 승객을 태웠다. 그리고 그 승객은 그에게 교차로 B로 가자고 했다. 단 그는 몇몇 사람들과 미팅을 갖기 위해 드라이브 도중 교차로 C₁, C₂, …, C_k를 거쳐야 한다. 단 이 중간 교차로들의 방문 순서는 중요하지 않다. 민승이는 위의 드라이브 조건을 만족하는 경로가 여럿 존재한다는 것을 깨달았지만 얼마나 많은지가 궁금해졌다.

입력

첫 번째 줄에 교차로의 개수인 N (1 ≤ N ≤ 1,000)과 도로의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다. 그 다음 M개에 줄에는 도로의 정보를 알려주는 시작점과 끝점이 주어진다. 다음 줄에는 시작점 A와 끝점 B, 그리고 방문해야할 중간 지점의 개수 K (0 ≤ K ≤ N-2)가 주어진다. 마지막 줄에는 공백을 구분으로 C₁, C₂, …, C_k가 차례대로 주어진다. 중간 지점에는 시작점과 끝점이 없다. 한 도시가 중간 지점에 두 번 이상 등장하는 경우는 없다.

출력

첫 번째 줄에 조건을 만족하는 경로의 개수 S를 출력한다. 경로가 존재하지 않을 경우엔 0을 출력한다. S가 2,000,000,000이 넘는 입력은 주어지지 않는다.

제한

힌트