힙 개수 세기

루트가 있는 트리가 주어진다. 트리는 $n$개의 정점으로 이루어져 있고, 각 정점에 $1$번부터 $n$번까지의 번호를 서로 겹치지 않게 하나씩 붙이려고 한다. 단, 모든 정점의 번호는 그 부모 정점의 번호보다 작아야 한다. 즉, 루트가 가장 큰 번호를 갖고, 부모에서 자식으로 내려갈수록 번호가 작아지는 최대 힙 구조를 이룬다.

이러한 번호 붙이기 방법의 수를 구하여라. 그 수가 매우 클 수 있으므로, $m$으로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $t$가 주어진다. ($1 \le t \le 250$)

각 테스트 케이스의 첫째 줄에는 트리의 정점 수 $n$과 나머지 연산에 사용할 값 $m$이 주어진다. ($1 \le n \le 500{,}000$, $2 \le m \le 10^{9}$)

이어지는 $n-1$개의 줄 중 $i$번째 줄에는 정점 $i+1$의 부모 정점 번호 $p_{i+1}$가 주어진다. ($1 \le p_{i+1} \le i$) 1번 정점은 항상 루트이다. 전체 입력의 크기는 50MB를 넘지 않는다.

각 테스트 케이스마다 조건을 만족하는 번호 붙이기 방법의 수를 $m$으로 나눈 나머지를 한 줄에 하나씩 출력한다.

예를 들어 예제의 마지막 경우($n=5$이고 정점 $2,3,4,5$의 부모가 각각 $1,1,3,3$인 트리)에서는 조건을 만족하는 번호 붙이기가 정확히 $8$가지이다.

$m$은 소수가 아닐 수도 있으므로, 나머지 연산에서 나눗셈(모듈러 역원)을 곧바로 사용할 수 없다는 점에 유의한다.