Problems
Bins and balls
Bins and balls
There are $n$ bins in a row. There is also an infinite supply of balls of $n$ distinct colors. Place exactly one ball into each bin, with the restriction that adjacent bins cannot contain balls of the same color. How many valid configurations of balls in bins are there?
\InputFile
One integer $n~(1 \le n \le 10^9)$.
\OutputFile
Print the number of valid configurations of balls in bins modulo $10^9 + 7$.
Input example #1
3
Output example #1
12