Hilbert Water Flooding

In a distant galaxy, a species called ccj discovered a group of low‐level creatures, the \(\mathsf{Hilbert}\) moles, living on \(\mathsf{Hilbert}\) planet in soil arranged as a \(\mathsf{Hilbert}\) curve. The ccj decided to attack by simply pouring water from above in order to drown them. Given an \(n\)th order Hilbert curve, your task is to determine how many unit areas will be flooded when water is poured from the top.

The Hilbert curve is constructed as follows. The base case \(h_1\) is a square of side length \(1\) with the top edge open. For \(i \ge 2\) the \(i\)th order curve \(h_i\) is constructed by taking 4 copies of \(h_{i-1}\) arranged in a \(2 \times 2\) grid. Before placing them, the top‐left copy is rotated \(90^\circ\) counterclockwise and the top–right copy is rotated \(90^\circ\) clockwise. Then, three extra unit segments (walls) are added to connect the four copies in the order left–up, left–down, right–down, and right–up. (See the figures for orders 1 to 4.)

The flooding process works as follows:

1. The topmost row of open cells (cells not blocked by a wall) is instantly flooded.
2. A cell will be flooded if and only if at least one of its three neighbors – the cell immediately above, to the left, or to the right – is flooded.

It can be shown that the flooded area \(A(n)\) satisfies the recurrence \[ A(1)=1, \quad A(n)=4\,A(n-1)+2 \quad \text{for } n \ge 2. \] In closed‐form, one may derive that \[ A(n)=\frac{5\cdot4^{n-1}-2}{3}. \] Since the answer can be very large, output it modulo \(M=9223372036854775783\).

Example:

For \(n=3\), we have \(A(3)=26\) (as illustrated in the sample image).

inputFormat

The input consists of a single line containing a positive integer \(n\) (\(1 \le n \le 10^{12}\), for example), representing the order of the Hilbert curve.

outputFormat

Output a single integer, the flooded area \(A(n)\) modulo \(9223372036854775783\).

sample

1

1