아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

도로망 설계도의 가짓수

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

요약
정점이 n개이고 지름이 정확히 d인 트리를 동형류 기준으로 세어 소수 p로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

유형
조합론, 트리, 동적 계획법, 정수론
정답자
아직 제출이 없습니다

문제

바이트맨(Byteman)이 바이트랜드(Byteland)를 자동차로 여행하려고 하지만, 나라의 지도를 구하지 못했습니다. 친구들에게서 도로망에 대한 몇 가지 사실만 전해 들었습니다.

  • 도시는 모두 nn개이며 11번부터 nn번까지 번호가 매겨져 있습니다.
  • 모든 도로는 양방향이며 서로 다른 두 도시를 잇습니다.
  • 서로 다른 두 도시 사이에는, 같은 도시를 두 번 지나지 않는 경로(도로 하나 이상으로 이루어진 길)가 정확히 하나 존재합니다.
  • 그러한 경로들 가운데 가장 긴 것은 도로를 정확히 dd개 사용합니다.

바이트맨은 이 정보와 모순되지 않는 도로망 설계도가 몇 가지인지 알고 싶어 합니다. 두 설계도는, 한쪽의 도시를 다른 쪽의 도시로 일대일 대응시켜 연결 관계가 완전히 같아지도록 만들 수 있으면 같은 것으로 봅니다. 즉 도시의 위치나 번호가 아니라 연결 구조만으로 비교합니다. 형식적으로, 첫 번째 설계도에서 두 도시가 도로로 이어져 있을 때 그에 대응하는 두 도시가 두 번째 설계도에서도 도로로 이어져 있는 일대일 대응이 존재하면, 두 설계도는 동일합니다.

경우의 수가 매우 클 수 있으므로 그 값을 pp로 나눈 나머지를 출력하세요.

입력

한 줄에 세 정수 nn, dd, pp가 공백 하나로 구분되어 주어집니다 (1≤n≤2001 \le n \le 200, 0≤d<n0 \le d < n, n<p≤109n < p \le 10^9, pp는 소수).

출력

바이트맨이 알고 있는 조건과 모순되지 않는 서로 다른 설계도의 개수를 pp로 나눈 나머지를 한 줄에 출력하세요.

힌트

예제4

  1. 예제 1

    입력
    6 3 13
    
    예상 출력
    2
    
  2. 예제 2

    입력
    1 0 2
    
    예상 출력
    1
    
  3. 예제 3

    입력
    3 2 5
    
    예상 출력
    1
    
  4. 예제 4

    입력
    5 3 7
    
    예상 출력
    1