레이팅 미적용소들은 농부 존의 새 금고를 열어 트랙터 열쇠를 손에 넣기로 맹세했다.
비밀번호 입력 시스템은 N개의 노드(1 <= N <= 20,000)로 이루어진 루트 트리 형태이며, 각 노드에는 0부터 9 사이의 숫자 하나가 필요하다. 노드의 번호는 0..N-1이다.
소들이 가진 유일한 정보는, 길이 5인 특정 수열들이 트리를 따라 위로 올라가는 특정 경로에는 나타나지 않는다는 것이다. 예를 들어 소들은 어떤 노드 F에서 시작해서(루트 방향으로 위로 읽으며) 수열 01234가 나타나지 않는다는 것을 알 수 있고, 이는 가능한 비밀번호 여러 개를 배제한다.
M개(1 <= M <= 50,000)의 길이 5 수열과 각각의 트리에서의 시작 노드가 주어질 때, 배제되는 비밀번호가 몇 개인지 소들이 알아내도록 도와라. 답은 1234567로 나눈 나머지로 계산해야 한다.
첫째 줄: 공백으로 구분된 두 정수 N과 M이 주어진다.
둘째 줄부터 N째 줄까지: i+1째 줄에는 트리에서 노드 i의 부모를 나타내는 정수 p(i)(0 <= p(i) < i) 하나가 주어진다.
N+1째 줄부터 N+M째 줄까지: N+i째 줄에는 나타나지 않는다고 알려진 i번째 수열이 주어진다. 이 줄에는 v(i)와 s(i)가 주어지는데, v(i)는 수열의 시작 노드이고, s(i)는 v(i)에서 시작해 트리를 따라 위로 올라가며 나타나지 않는다고 알려진 5자리 문자열이다. 루트는 v(i)로부터 위쪽으로 최소 4단계 떨어져 있음이 보장된다.
배제되는 구성의 개수를 1234567로 나눈 나머지를 정수 하나로 출력한다.
code.in · 출력을 쓸 파일 code.out6 2
0
1
2
3
3
4 01234
5 9123419