Ящики і кулі

У ряду стоять $n$ ящиків. У вас є необмежена кількість кульок $n$ різних кольорів. Розмістіть по одній кульці в кожен ящик так, щоб у сусідніх ящиках не було кульок одного кольору. Скільки існує різних варіантів розміщення кульок по ящиках?

Вхідні дані

Одне ціле число $n(1\le n\le 10^9)$.

Вихідні дані

Виведіть кількість різних варіантів розміщення кульок по ящиках, обчислену за модулем $10^9+7$.

Приклади