题目背景

注，此题和 CQOI 的鼹鼠不一样，请仔细看题！本题只是借用背景！

在茫茫宇宙中……

题目描述

有一群生物 ccj，他们在上次的星系中，发现了一群低等生物，于是想进行一波黑暗森林打击。这群低等生物即是 $\mathsf{Hilbert}$ 鼹鼠，生活在 $\mathsf{Hilbert}$ 星球，住在 $\mathsf{Hilbert}$ 曲线土壤内。
这群生物决定用最傻的办法——灌水，来淹死他们。现在“高等”生物想知道，对于 $n$ 阶的 $\mathsf{Hilbert}$ 曲线，从上往下灌水，能淹没几个单位面积？

这是 $1 \sim 4$ 阶的 $\mathsf{Hilbert}$ 曲线：

$h_1$，如最左图所示，是一个缺上口的正方形，这个正方形的边长为 $1$。 从$h_2$ 开始，按照以下方法构造曲线 $h_i$： 将 $h_{i-1}$ 复制四份，按 $2\times2$ 摆放。
把左上一份逆时针转 $90^{\circ }$，右上一份顺时针转 $90^{\circ }$，然后用三条单位线段将四分曲线按照左上-左下-右下-右上的顺序连接起来。如图所示，分别展示的是 $h_2$，$h_3$，$h_4$。加粗的线段是额外用于连接的线段。

灌水方式：

（显然这个是 $h_3$ 的灌水面积）绿色即为无法被灌到的地方，红色为可以灌到的地方，灰色为墙，所以答案是 $26$，即为样例1。

一个方格有水当且仅当在它的上，左，右方格中有至少一个方格有水，最上面一层的空格都有水。

注，此题要求对 $9223372036854775783$ 取模

输入格式

一个整数 $n$，表示这个洞穴是 $n$ 阶的 $\mathsf{Hilbert}$ 曲线。

输出格式

一个整数 $ans$，表示有 $ans$ 个单位面积被淹没。

3

26

4

100

12

2137408

提示

样例解释：

自己数一数嘛……

$n \le 10^{10000}$

详细范围参见“标程”

数据均为手动构造，请注意常数！