eolymp
bolt
Try our new interface for solving problems
Problems

Bins and balls

Bins and balls

Time limit 1 second
Memory limit 128 MiB

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?

Input data

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

Output data

Print the number of valid configurations of balls in bins modulo 10^9 + 7.

Examples

Input example #1
3
Output example #1
12