담유는 샹들리에 제작의 대가로, 무려 년 동안 샹들리에를 만들어 왔다.
그의 샹들리에는 원형 틀 위에 놓인 개의 레몬으로 이루어져 있다. 사용할 수 있는 색은 총 종류이며, 같은 색의 레몬을 여러 개 사용하는 것도 가능하다. 각 색의 레몬은 충분히 많이 준비되어 있다.
담유는 오랜 경험을 통해 다음 조건을 만족할 때만 샹들리에가 아름답다는 사실을 알아냈다.
와 , 과 끼리 색이 같고, 와 은 색이 다른 서로 다른 네 레몬 쌍 에 대해 선분 와 선분 는 서로 교차하지 않아야 한다.
가능한 샹들리에는 총 개 존재한다. 이 중 아름다운 샹들리에의 개수를 로 나눈 나머지를 구하여라.
단, 두 샹들리에가 회전을 통해 서로 일치하더라도 서로 다른 것으로 간주한다.
입력은 다음과 같이 주어진다.
아름다운 샹들리에의 개수를 로 나눈 나머지를 출력한다.
