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

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

Обмеження

• ~1≤n≤10^9~

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

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

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

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

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

4

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

16456