Problem Background

Note, this problem is different from the mole problem in CQOI. Please read the problem carefully! This problem merely borrows the background!

In the vast universe...

Problem Description

There is a group of creatures called ccj. In their previous galaxy, they discovered a group of inferior creatures, the $\mathsf{Hilbert}$ moles, living on the $\mathsf{Hilbert}$ planet within the $\mathsf{Hilbert}$ curve soil. These creatures decided to use the most naive method—flooding—to drown them. Now, the "advanced" creatures want to know, for an $n$-th order $\mathsf{Hilbert}$ curve, how many unit areas can be flooded from top to bottom?

Here are the $\mathsf{Hilbert}$ curves for orders 1 through 4:

$h_1$, as shown in the leftmost figure, is a square with a missing top side, with a side length of 1. Starting from $h_2$, the curve $h_i$ is constructed as follows: Duplicate $h_{i-1}$ four times and arrange them in a $2\times2$ grid. Rotate the top-left copy counterclockwise by $90^{\circ}$ and the top-right copy clockwise by $90^{\circ}$. Then, connect the four parts with three unit segments in the order of top-left, bottom-left, bottom-right, and top-right. The figures show $h_2$, $h_3$, and $h_4$, respectively. The bold segments are the additional connecting segments.

Flooding method:

(This clearly shows the flooded area for $h_3$) Green areas are unreachable, red areas are reachable, and gray areas are walls. Therefore, the answer is 26, which is the sample output for Sample 1.

A grid is flooded if and only if at least one of its adjacent grids (up, left, right) is flooded, and the empty grids in the top row are all flooded.

Note, this problem requires the result to be modulo $9223372036854775783$.

Input Format

A single integer $n$, indicating that the cave is an $n$-th order $\mathsf{Hilbert}$ curve.

Output Format

A single integer $ans$, indicating that $ans$ unit areas are flooded.

Sample Input and Output

Sample Input #1

3

Sample Output #1

26

Sample Input #2

4

Sample Output #2

100

Sample Input #3

12

Sample Output #3

2137408

Notes

Sample Explanation:

Count it yourself...

$n \le 10^{10000}$

Refer to the "standard solution" for detailed ranges.

The data is manually constructed, please pay attention to constants!

见题面 Input 部分

见题面 Output 部分