链接: https://cses.fi/problemset/task/2210

板块: Mathematics

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你的任务是计数每个方格为黑色或白色的不同 $n \times n$ 网格的数量。

如果无法通过旋转其中一个网格使它们看起来相同，则认为两个网格是不同的。

输入

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

输出

输出一个整数：网格数量对 $10^9+7$ 取模的结果。

数据范围

$1 \le n \le 10^9$

样例输入

4

样例输出

16456