#2 Lemon chandelier

Statement

Statement language

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 having same color, and and having different color implies line segment and 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.

Input

The input is given in the following format:

$N$

Output

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

Constraints

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

Subtasks

#	Score	Constraints
1	52	$N \le 5 \ 000$
2	48	There are no additional constraints.

Samples

Sample 1

Input

3

Output

27

Sample 2

Input

4

Output

244

Sample 3

Input

2025

Output

773843905