택시

서울에는 1번부터 N번까지 번호가 붙은 N개의 교차로가 있다. 일부 교차로 사이에는 좁은 일방통행 도로가 놓여 있다. 도로망에는 어떤 교차로에서 출발해 다시 그 교차로로 돌아오는 경로가 없고, 같은 방향으로 같은 두 교차로를 잇는 도로가 두 개 이상 존재하지 않는다.

민승이는 교차로 A에서 승객을 태웠고, 승객은 교차로 B까지 가기를 원한다. 이 승객은 이동하는 동안 미팅을 위해 교차로 C1, C2, ..., Ck를 모두 방문해야 한다. 이 중간 교차로들을 방문하는 순서는 정해져 있지 않다.

민승이는 조건을 만족하는 경로가 여러 개일 수 있음을 알게 되었다. 조건을 만족하는 경로의 개수를 구하라.

첫째 줄에 교차로의 개수 N (1 <= N <= 1,000)과 도로의 개수 M (1 <= M <= 1,000,000)이 주어진다.

다음 M개의 줄에는 도로의 시작 교차로와 도착 교차로가 주어진다.

도로 정보 다음에는 출발점 A, 도착점 B, 반드시 방문해야 하는 중간 교차로의 개수 K (0 <= K <= N - 2)가 차례로 주어진다.

이후 C1, C2, ..., Ck가 공백으로 구분되어 주어진다. 중간 교차로에는 출발점과 도착점이 포함되지 않으며, 같은 교차로가 두 번 이상 등장하지 않는다.

조건을 만족하는 경로의 개수 S를 출력한다. 조건을 만족하는 경로가 없다면 0을 출력한다.

S가 2,000,000,000을 넘는 입력은 주어지지 않는다.