34822번 - 함수동상 그래프

$N$개의 정점과 $N$개의 단방향 간선으로 이루어진 그래프가 주어진다. 각 정점에는 $1$부터 $N$까지 번호가 매겨져 있다. 각 정점은 정확히 하나의 나가는 간선을 가지며, 그중 $i$번 정점에서 나가는 간선의 도착 정점은 $e_i$번 정점이다. $(1\le i, \, e_i \le N)$ 자기 자신으로 돌아가는 간선 역시 존재할 수 있다.

이 그래프의 정점 중 $K$개의 정점 위에는 동상이 하나씩 놓여 있다. 이때 다음 행동을 $0$회 이상 원하는 만큼 실행할 수 있다.

• $i$번 정점의 동상을 선택해 간선을 따라 $e_i$번 정점으로 옮긴다. $i$번 정점에는 동상이 놓여 있어야 하며, $e_i$번 정점에는 동상이 없어야 한다.

원하는 만큼 행동을 수행한 뒤, 동상이 올라가 있는 정점의 집합으로 가능한 경우의 수를 구해 보자.

첫째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $(1\le K\le N\le 8\, 000)$

둘째 줄에 각 정점에서 나가는 간선의 도착 정점의 번호를 나타내는 $N$개의 정수 $e_1, \cdots, e_N$이 공백으로 구분되어 주어진다.

셋째 줄에 각 동상이 놓여 있는 정점의 번호를 나타내는 $K$개의 서로 다른 양의 정수가 공백으로 구분되어 오름차순으로 주어진다.

첫째 줄에 동상이 올라가 있는 정점의 집합으로 가능한 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다. $10^9+7$은 소수다.