시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 23 8 8 44.444%

문제

먼 옛날, N개의 섬들로 이루어진 섬나라가 있었다. 섬들은 모양이 모두 같아 구별할 수 없었다.

섬들 사이에는 다리가 없었기 때문에, 섬들 사이를 이동하려면 배를 타야 했다. 주민들은 의논 끝에, 섬들 사이를 연결하는 다리를 짓기로 했다.

다리를 아무렇게나 지으면 엉망이 될 수 있기 때문에, 다리를 짓는 데 아래와 같은 세 가지 조건을 두었다.

  1. 다리를 지었을 때, 모든 섬들이 연결되어 있어야 한다. 즉, 다리를 통해 임의의 두 섬 사이를 이동할 수 있어야 한다.
  2. 건설 비용을 아끼기 위해, 다리의 개수는 최소가 되어야 한다.
  3. 한 섬에 다리가 너무 많이 연결되면 교통망이 마비될 수 있기 때문에, 한 섬에는 최대 네 개의 다리만 지어질 수 있다.

예를 들어, N=6인 경우 왼쪽 방법은 가능한 건설 방법이지만, 오른쪽 방법은 불가능한 건설 방법이다.

다리를 짓는 방법이 총 몇 가지인지 구해 보자. 섬들은 구별되지 않는다고 가정한다.

입력

첫 줄에 섬의 수 N과 X가 주어진다. (1 ≤ N ≤ 3000, 109​ ≤ X ≤ 109+104, X는 소수)

X의 용도는 출력 부분을 참고하자.

출력

다리를 짓는 방법의 수를 출력한다. 답이 매우 커질 수 있으므로, X로 나눈 나머지를 출력한다.

섬들은 구별되지 않는다고 가정한다.

예제 입력 1

4 1000000007

예제 출력 1

2

N=4일 때, 가능한 다리 건설 방법은 위와 같은 2가지뿐이다.

출처

High School > 서울과학고등학교 > 2020 SciOI #1 E번

  • 문제를 만든 사람: 79brue