В ряду стоят n ящиков. Имеется неограниченное количество шаров n различных цветов. Поместите по одному шару в каждый ящик таким образом, чтобы два соседних ящика не содержали шары одного цвета. Сколько имеется различных расположений шаров по ящикам?
Одно целое число n (1≤n≤109).
Выведите количество различных расположений шаров по ящикам, вычисленное по модулю 109+7.