시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 57 | 14 | 13 | 28.261% |
먼 옛날, N개의 섬들로 이루어진 섬나라가 있었다. 섬들은 모양이 모두 같아 구별할 수 없었다.
섬들 사이에는 다리가 없었기 때문에, 섬들 사이를 이동하려면 배를 타야 했다. 주민들은 의논 끝에, 섬들 사이를 연결하는 다리를 짓기로 했다.
다리를 아무렇게나 지으면 엉망이 될 수 있기 때문에, 다리를 짓는 데 아래와 같은 세 가지 조건을 두었다.
예를 들어, N=6인 경우 왼쪽 방법은 가능한 건설 방법이지만, 오른쪽 방법은 불가능한 건설 방법이다.
다리를 짓는 방법이 총 몇 가지인지 구해 보자. 섬들은 구별되지 않는다고 가정한다.
첫 줄에 섬의 수 N과 X가 주어진다. (1 ≤ N ≤ 3000, 109 ≤ X ≤ 109+104, X는 소수)
X의 용도는 출력 부분을 참고하자.
다리를 짓는 방법의 수를 출력한다. 답이 매우 커질 수 있으므로, X로 나눈 나머지를 출력한다.
섬들은 구별되지 않는다고 가정한다.
4 1000000007
2
N=4일 때, 가능한 다리 건설 방법은 위와 같은 2가지뿐이다.
High School > 서울과학고등학교 > 2020 SciOI #1 E번