도로망 설계도의 가짓수
시간 제한1초메모리 제한128 MB
정점이 n개이고 지름이 정확히 d인 트리를 동형류 기준으로 세어 소수 p로 나눈 나머지를 구한다.
문제
바이트맨(Byteman)이 바이트랜드(Byteland)를 자동차로 여행하려고 하지만, 나라의 지도를 구하지 못했습니다. 친구들에게서 도로망에 대한 몇 가지 사실만 전해 들었습니다.
- 도시는 모두 개이며 번부터 번까지 번호가 매겨져 있습니다.
- 모든 도로는 양방향이며 서로 다른 두 도시를 잇습니다.
- 서로 다른 두 도시 사이에는, 같은 도시를 두 번 지나지 않는 경로(도로 하나 이상으로 이루어진 길)가 정확히 하나 존재합니다.
- 그러한 경로들 가운데 가장 긴 것은 도로를 정확히 개 사용합니다.
바이트맨은 이 정보와 모순되지 않는 도로망 설계도가 몇 가지인지 알고 싶어 합니다. 두 설계도는, 한쪽의 도시를 다른 쪽의 도시로 일대일 대응시켜 연결 관계가 완전히 같아지도록 만들 수 있으면 같은 것으로 봅니다. 즉 도시의 위치나 번호가 아니라 연결 구조만으로 비교합니다. 형식적으로, 첫 번째 설계도에서 두 도시가 도로로 이어져 있을 때 그에 대응하는 두 도시가 두 번째 설계도에서도 도로로 이어져 있는 일대일 대응이 존재하면, 두 설계도는 동일합니다.
경우의 수가 매우 클 수 있으므로 그 값을 로 나눈 나머지를 출력하세요.
입력
한 줄에 세 정수 , , 가 공백 하나로 구분되어 주어집니다 (, , , 는 소수).
출력
바이트맨이 알고 있는 조건과 모순되지 않는 서로 다른 설계도의 개수를 로 나눈 나머지를 한 줄에 출력하세요.
힌트
