Lemon chandelier

Damyoo is a master at chandelier, who has been making it for $49$ years. His chandelier is made with $N$ lemons with various colors on top of circular frame. $N$ types of colors can be used, and lemons with same colors can be used multiple times. There are enough lemons of each color. Damyoo, by his experience, noticed that a chandelier is beautiful only if the following holds:

For any four distinct lemons $P, Q, R,$ and $S$, $P$ and $Q$ having same color, $R$ and $S$ having same color, and $P$ and $R$ having different color implies line segment $PQ$ and $RS$ does not intersect.

For $N^N$ possible different chandeliers, find the number of beautiful chandelier. Note that two chandeliers are considered different even though they become same after some rotation.

The input is given in the following format:

$N$

Print one integer on the first line: the number of beautiful chandeliers modulo $10^9+7$.

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