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$은 소수다.

제한

노트