길이가 인 수열 가 주어진다. 수열에는 부터 까지의 각 정수가 정확히 두 번씩 등장한다.
원소들의 삭제 순서를 모든 개의 순서 중 하나로 균등하게 선택한다. 선택한 순서대로 원래의 원소를 하나씩 삭제하며, 남은 원소들의 상대적인 순서는 유지된다.
삭제를 시작하기 전 또는 삭제 도중에 정수 의 두 원소가 한 번이라도 인접하면 점을 얻는다. 각 정수에 대한 점수는 한 번만 얻는다. 최종 점수를 라 할 때, 의 기댓값을 구하여라.
기댓값을 기약분수 로 나타내었을 때, 을 으로 나눈 나머지를 출력한다. 여기서 은 을 법으로 하는 의 곱셈 역원이다.
입력은 다음과 같은 형식으로 주어진다.
의 기댓값을 을 법으로 하여 출력한다.
삭제를 시작하기 전부터 두 이 인접하므로 반드시 점을 얻는다. 따라서 이고 이다.
첫 번째로 가운데 두 원소 중 하나를 삭제하면, 그 다음에 어떤 원소를 삭제하더라도 정확히 한 정수가 점수를 얻는다. 첫 번째로 양 끝 원소 중 하나를 삭제하면, 남은 세 원소 중 가운데 원소를 두 번째로 삭제할 때만 점수를 얻는다.
따라서 일 확률은 이고, 나머지 경우에는 이다. 그러므로 이며 이를 주어진 법으로 나타내면 이다.
두 는 처음부터 인접하므로 반드시 점을 얻는다. 두 도 인접하려면 두 가 모두 두 보다 먼저 삭제되어야 한다. 이 확률은 이다.
따라서 일 확률은 , 일 확률은 이므로 이다. 이를 주어진 법으로 나타내면 이다.
