금고 해독

시간 제한1초메모리 제한128 MB

요약

루트 트리 각 노드에 숫자를 배정할 때 지정된 위쪽 경로에 금지된 5자리 숫자열이 하나라도 나타나는 경우의 수를 1234567로 나눈 나머지를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 트리, 조합론
정답자: 아직 제출이 없습니다

문제

소들이 농장주 존의 트랙터를 몰고 다니다가 트러블을 일으켜, 존은 트랙터 열쇠를 사무실 금고에 넣어 두었다. 소들은 이 금고를 열기로 결심했다.

금고는 트리 형태의 복잡한 비밀번호 시스템으로 보호된다. 비밀번호 입력은 $N$ 개의 노드로 이루어진 루트 트리이며, 각 노드에는 0부터 9까지의 숫자 하나가 들어간다. 노드는 0부터 $N-1$ 까지 번호가 붙는다.

소들이 아는 정보는, 트리 위쪽으로 올라가는 특정 경로에서 길이 5인 특정 수열이 나타나지 않는다는 것뿐이다. $M$ 개의 길이 5 수열과 각 수열의 시작 노드가 주어질 때, 더 이상 가능하지 않게 된 전체 비밀번호 배정의 개수를 구하라. 답은 $1234567$ 로 나눈 나머지를 출력한다.

입력

첫 줄: 공백으로 구분된 두 정수 $N$ , $M$
다음 $N-1$ 줄: $i+1$ 번째 줄에 노드 $i$ 의 부모 $p(i)$ ( $0 \leq p(i) < i$ )
다음 $M$ 줄: $v(i)$ 와 $s(i)$ . $v(i)$ 는 시작 노드, $s(i)$ 는 $v(i)$ 에서 위쪽으로 5칸 올라가며 나타나지 않는 5자리 문자열. $v(i)$ 에서 루트까지 최소 4단계 위에 있음이 보장된다.

출력

배제된 배정의 개수를 $1234567$ 로 나눈 나머지 하나를 출력한다.

예제3

예제 1
입력
```
6 2
0
1
2
3
3
4 01234
5 91234
```
예상 출력
```
19
```
예제 2
입력
```
6 1
0
1
2
3
4
5 01234
```
예상 출력
```
10
```
예제 3
입력
```
8 2
0
1
2
3
4
5
6
7 01234
6 98765
```
예상 출력
```
2000
```