Bins and balls#9557

Bins and balls

1 second

128 megabytes

Very easy

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 \leq n \leq 1 0^{9})$ n~(1 \le n \le 10^9).

Output

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

Examples

Example 1

Loading

n (1 \leq n \leq 1 0^{9})

1 0^{9} + 7