题目背景

翻译自 CSES-2210 题。

题目描述

你的任务是计算有多少种不同的 $n×n$ 网格，其中每个格子可以是黑色或白色。

两个网格被认为是不同的，当且仅当无法通过旋转其中一个网格使其与另一个网格完全相同。

输入格式

唯一的输入行包含一个整数 $n$：表示网格的大小。

输出格式

输出不同网格的数量，结果对 $10^9+7$ 取模。

样例

4

16456

说明/提示

$1 \leq n \leq 10^9$。