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