레몬 샹들리에

시간 제한1초메모리 제한1024 MB

요약

원 위에 놓인 N개의 레몬을 N가지 색으로 칠할 때, 같은 색 두 점을 이은 선분이 다른 색 선분과 교차하지 않는 색칠의 수를 센다.

문제

담유는 $49$ 년간 샹들리에를 만들어 온 장인이다. 그의 샹들리에는 원형 프레임 위에 다양한 색의 레몬을 $N$ 개 매달아 완성된다. 사용 가능한 색의 수는 $N$ 가지이며, 같은 색의 레몬을 여러 개 사용할 수 있다. 각 색의 레몬은 충분히 많다.

그는 오랜 경험을 통해 다음 조건을 만족해야 샹들리에가 아름답다는 사실을 깨달았다.

임의의 서로 다른 네 개의 레몬 $P, Q, R, S$ 에 대해 $P$ 와 $Q$ 의 색이 같고 $R$ 과 $S$ 의 색이 같으며 $P$ 와 $R$ 의 색이 다르다면, 선분 $PQ$ 와 $RS$ 는 교차하지 않아야 한다.

가능한 모든 $N^N$ 개의 샹들리에 중에서 아름다운 샹들리에의 개수를 구하여라. 단, 회전하여 같은 모양이 되더라도 서로 다른 샹들리에로 취급한다.

입력은 다음과 같은 형식으로 주어진다.

$N$

첫째 줄에 만들 수 있는 아름다운 샹들리에의 개수를 $10^9+7$ 로 나눈 나머지를 출력한다.