Ваше завдання полягає в тому, щоб підрахувати кількість різних \(n × n\) граток, у яких кожен квадрат чорний або білий.

Дві гратки вважаються різними, якщо неможливо повернути одну з них так, щоб вони виглядали однаково.

Обмеження

• \(1≤n≤10^9\)

Формат вхідних даних

Єдиний рядок вхідних даних містить ціле число \(n\): розмір гратки.

Формат вихідних даних

Вивести одне ціле число: кількість граток за модулем \(10^9+7\).

Приклад вхідних даних

4

Приклад вихідних даних

16456