Ящики і кульки#9557
У ряд стоїть ящиків. У вас є необмежена кількість кульок різних кольорів. Розмістіть по одній кульці в кожний ящик таким чином, щоб у сусідніх ящиках не було кульок одного кольору. Скільки існує різних варіантів розміщення кульок по ящиках?
Одне ціле число n~(1 \le n \le 10^9).
Виведіть кількість різних варіантів розміщення кульок по ящиках, обчислену за модулем 10^9 + 7.
Приклад 1