34249번 - 레몬 샹들리에 서브태스크

문제

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

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

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

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

입력

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

$N$

출력

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

제한

• 3ドル \leq N \leq 1\ 000\ 000$.

서브태스크

힌트