Bins and balls

There are $n$ boxes arranged in a row. You have an unlimited supply of balls in $n$ different colors. Place one ball in each box in such a way that no two adjacent boxes contain balls of the same color. How many different arrangements of balls in the boxes are possible?

Input

One integer $n(1\le n\le 10^9)$.

Output

Print the number of different arrangements of balls in the boxes, computed modulo $10^9+7$.

Examples