Без подвоєнь

Обмеження: 2 сек., 256 МіБ

Зеник і Марічка вивчають різні аспекти англійської мови.

Сьогодні їх цікавить скільки існує різних рядків довжини \(n\), які можна утворити із малих букв англійського алфавіту (a-z), у яких жодні дві сусідні букви не є однаковими?

Оскільки відповідь може бути великою, виведіть остачу від ділення відповіді на число \(10^9+7\).

Вхідні дані

У першому рядку задано одне ціле число \(n\) — довжина рядків.

Вихідні дані

У єдиному рядку виведіть одне ціле число — відповідь на задачу по модулю \(10^9+7\).

Обмеження

\(1 \le n \le 10^5\).

Приклади

Вхідні дані (stdin)	Вихідні дані (stdout)
1	26

Вхідні дані (stdin)	Вихідні дані (stdout)
2	650

Вхідні дані (stdin)	Вихідні дані (stdout)
3	16250

Вхідні дані (stdin)	Вихідні дані (stdout)
47	987831870

Примітки

У першому прикладі усі рядки із однієї букви підходять.

У другому прикладі підходять усі рядки із двох букв окрім aa, bb, ... zz.

Element Type	Створено	Хто	Задача	Компілятор	Результат	Час (сек.)	Пам'ять (МіБ)	№	Дії