산책

어느 날 아침, 라즈바란은 친구 두 명인 매튜와 피터를 잘 알려진 공원으로 산책에 초대했다. 이 공원은 n개의 노드(1번부터 n번까지)로 이루어진 트리 모양이고, n-1쌍의 노드 사이에는 10미터 길이의 산책로가 있다. 각 i번 노드에는 i번 샘물이 있다. 친구들은 다음 규칙을 지키는 산책만 받아들인다. 매튜는 거만한 청년이라서 가능한 한 적은 미터를 걸어 모든 샘물에 도착하기를 원하고, 피터는 도전을 받아들이겠다며 미리 정해진 순서 P1, P2, …, Pm대로 m개의 샘물을 방문하고 싶다고 말한다. 라즈바란은 이제 두 사람이 몇 가지 방법으로 걸을 수 있는지 궁금해한다. 입구와 출구 모두 첫 번째 샘물에 있고, 그 샘물은 동시에 트리의 뿌리이다.

세 친구가 걸을 수 있는 방법의 수를 구하시오. 이 수는 109+7로 나눈 나머지로 출력해야 한다.

입력의 첫 줄에는 두 양의 정수 n과 m이 주어지며, 이는 공원의 샘물 수와 피터가 방문하고 싶어 하는 샘물 수를 나타낸다. 다음 줄에는 n-1개의 수 T2, T3, …, Tn이 주어지며, 이는 트리에 대응하는 부모 배열을 나타낸다. 그다음 줄에는 m개의 서로 다른 수 P1, P2, …, Pm이 주어진다.

출력의 첫 줄에 구한 수를 출력하시오.

• 2 ≤ m ≤ n ≤ 400.000
• 공원의 모양이 트리(비순환, 연결, 무방향 그래프)임이 보장된다.

세 친구가 걸을 수 있는 올바른 방법은 다음과 같다.

• 1 2 5 2 4 2 6 2 1 3 7 3 1
• 1 2 6 2 5 2 4 2 1 3 7 3 1
• 1 2 5 2 6 2 4 2 1 3 7 3 1

또한, 올바르지 않은 산책 세 가지는 다음과 같다.

• 1 2 5 2 4 2 1 3 7 3 1 (6번 샘물을 방문하지 않았다)
• 1 2 4 2 5 2 6 2 1 3 7 3 1 (5번 샘물보다 4번 샘물을 먼저 방문했다)
• 1 2 4 2 5 2 6 2 4 2 1 3 7 3 1 (산책의 길이가 최소가 아니다)