연극 배역

N명의 배우가 연극을 준비한다. 연극은 여러 장면으로 구성되며, 각 장면마다 일부 배우만 무대에 선다. 배우가 무대에 오르거나 내릴 때마다 "전환"이 발생한다.

최소 전환 횟수로 가능한 한 많은 장면을 만들고자 한다. 장면은 서로 다른 배역 조합이어야 하며, 빈 장면(아무도 없는 장면)도 포함한다. 단, 연속된 두 장면에서 모든 배우의 등장/퇴장 상태가 달라야 한다(즉, 각 배우는 이전 장면과 현재 장면에서 정확히 하나의 상태 변화가 있어야 한다).

최소 전환으로 만들 수 있는 최대 장면 수를 구하는 프로그램을 작성하시오.

입출력 예시

입력 1