Ящики и шары

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

Входные данные

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

Выходные данные

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

Примеры