문제

잘 알려지지 않은 알고리즘 온라인 져지인 말고스팟은 ANIM-MALGO(아님-말고)라는 새로운 방식으로 채점을 한다. 말고스팟의 문제들은 각자 여러 개의 데이터를 가지고 있고, 그 데이터를 순차적으로 대입한다는 점에서는 알고스팟과 동일하다.

알고스팟과의 차이점은 말고스팟의 정답 판단은 각 데이터마다 답안들간의 다수결로 정해진다는 것이다. 또한 오답으로 처리된 답안들은 그 이후의 데이터에서 고려되지 않는다. 만약에 정확하게 균등한 분포로 나누어져서 다수 의견이 존재하지 않는다면, 그중 가장 먼저 제출한 사람의 답안을 정답으로 고려한다.

당신은 말고스팟에 'Yes' 혹은 'No'를 출력하는 문제를 냈는데, 데이터를 만들기 귀찮은 나머지 모든 테스트 케이스의 답을 'Yes'로 만들었다. 그러나 시간이 지나면서 몇몇 데이터에 대해 'No'를 출력하는 답안들이 등장하기 시작했다. 그 결과, 문제를 올바르게 푼 사람도 오답을 받는 사태에 도달했다.

당신은 이 문제를 해결하기로 했으나 새로운 데이터를 만드는 것은 상당히 귀찮은 일이므로, 먼저 기존의 데이터 순서를 바꿔서 'Yes'를 출력하는 사람들이 정답을 받게 하고 싶다. 다행인 점은 첫 번째 답안은 모두 Yes를 출력하는 정답 코드였기 때문에, 첫 번째 답안이 아직 유효하고 'Yes'를 출력한 답안과 'No'를 출력한 답안의 수가 같으면 'Yes'가 정답으로 인정된다는 것이다.

예를 들어 총 5개의 답안 중에 각 데이터에 대해 'No'를 출력하는 답안들의 정보들이 다음과 같다고 하자:

이때 기존의 순서인 1→2→3→4→5$1→2→3→4→5$ 순서대로 채점한다면 유효한 답안의 번호들은 다음과 같이 변화한다.

따라서 2번, 3번 데이터가 "No"로 채점되게 된다.

반면 순서를 바꾸어 데이터를 1→3→2→4→5$1→3→2→4→5$ 순서대로 채점한다면 유효한 답안의 번호들은 다음과 같이 변화한다.

따라서 이 경우에는 모든 데이터에서 Yes가 정답으로 인정받게 된다.

당신은 천재이기 때문에 눈으로 보고 한 번에 데이터들의 순서를 정할 수 있었다. 이제 남은 궁금증은 이처럼 모든 데이터의 답을 Yes로 만들 수 있는 순열의 수가 몇 가지인지 추측하는 것이다.