금고 해독

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

금고는 트리 형태의 복잡한 비밀번호 시스템으로 보호된다. 비밀번호 입력은 $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$로 나눈 나머지 하나를 출력한다.