Без подвоєнь

Limits: 2 sec., 256 MiB

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

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

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

Input

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

Output

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

Constraints

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

Samples

Input (stdin) сopy	Output (stdout) сopy
1	26

Input (stdin) сopy	Output (stdout) сopy
2	650

Input (stdin) сopy	Output (stdout) сopy
3	16250

Input (stdin) сopy	Output (stdout) сopy
47	987831870

Notes

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

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