#CS2210. 计算网格数量

计算网格数量

题目背景

翻译自 CSES-2210 题。

题目描述

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

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

输入格式

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

输出格式

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

样例

4

16456

说明/提示

$1 \leq n \leq 10^9$