레몬 샹들리에

담유는 샹들리에 제작의 대가로, 무려 $49$년 동안 샹들리에를 만들어 왔다.

그의 샹들리에는 원형 틀 위에 놓인 $N$개의 레몬으로 이루어져 있다. 사용할 수 있는 색은 총 $N$종류이며, 같은 색의 레몬을 여러 개 사용하는 것도 가능하다. 각 색의 레몬은 충분히 많이 준비되어 있다.

담유는 오랜 경험을 통해 다음 조건을 만족할 때만 샹들리에가 아름답다는 사실을 알아냈다.

$P$와 $Q$, $R$과 $S$ 끼리 색이 같고, $P$와 $R$은 색이 다른 서로 다른 네 레몬 쌍 $P, Q, R, S$에 대해 선분 $PQ$와 선분 $RS$는 서로 교차하지 않아야 한다.

가능한 샹들리에는 총 $N^N$개 존재한다. 이 중 아름다운 샹들리에의 개수를 $10^9+7$로 나눈 나머지를 구하여라.

단, 두 샹들리에가 회전을 통해 서로 일치하더라도 서로 다른 것으로 간주한다.

입력은 다음과 같이 주어진다.

$N$

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

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