도로망 설계도의 가짓수

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

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

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

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

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

입력

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

출력

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

힌트