Задачі
Ящики и шары
Ящики и шары
В ряду стоят $n$ ящиков. Имеется неограниченное количество шаров $n$ различных цветов. Поместите по одному шару в каждый ящик таким образом, чтобы два соседних ящика не содержали шары одного цвета. Сколько имеется различных расположений шаров по ящикам?
\InputFile
Одно целое число $n~(1 \le n \le 10^9)$.
\OutputFile
Выведите количество различных расположений шаров по ящикам, вычисленное по модулю $10^9 + 7$.
Вхідні дані #1
3
Вихідні дані #1
12