18802번 - Bridge Construction

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

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

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

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

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

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

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

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

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

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