黑暗打击

题目背景

注,此题和 CQOI 的鼹鼠不一样,请仔细看题!本题只是借用背景! 在茫茫宇宙中……

题目描述

有一群生物 ccj,他们在上次的星系中,发现了一群低等生物,于是想进行一波黑暗森林打击。这群低等生物即是 $\mathsf{Hilbert}$ 鼹鼠,生活在 $\mathsf{Hilbert}$ 星球,住在 $\mathsf{Hilbert}$ 曲线土壤内。 这群生物决定用最傻的办法——灌水,来淹死他们。现在“高等”生物想知道,对于 $n$ 阶的 $\mathsf{Hilbert}$ 曲线,从上往下灌水,能淹没几个单位面积? 这是 $1 \sim 4$ 阶的 $\mathsf{Hilbert}$ 曲线: ![](https://cdn.luogu.com.cn/upload/pic/28912.png) $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。 ![](https://cdn.luogu.com.cn/upload/pic/40229.png) 一个方格有水当且仅当在它的上,左,右方格中有至少一个方格有水,最上面一层的空格都有水。 注,此题要求对 $9223372036854775783$ 取模

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

3

输出样例 #1

26

输入样例 #2

4

输出样例 #2

100

输入样例 #3

12

输出样例 #3

2137408

说明

**样例解释:** 自己数一数嘛…… $n \le 10^{10000}$ 详细范围参见“标程” 数据均为手动构造,请注意常数!