黑暗打击

题目背景

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

题目描述

有一群生物ccj,他们在上次的星系中,发现了一群低等生物,于是想进行一波黑暗森林打击。这群低等生物即是$Hilbert$鼹鼠,生活在$Hilbert$星球,住在$Hilbert$曲线土壤内。这群生物决定用最傻的办法——灌水,来淹死他们。现在“高等”生物想知道,对于$n$阶的$Hilbert$曲线,从上往下灌水,能淹没几个单位面积? 这是$1$~$4$阶的$Hilbert$曲线: ![fuck](https://cdn.luogu.org/upload/pic/28912.png) $H1$,如最左图所示,是一个缺上口的正方形,这个正方形的边长为$1$。 从$H2$开始,按照以下方法构造曲线$Hi$: 将$Hi-1$复制四份,按$2*2$摆放。把左上一份逆时针转$90^{\circ }$,右上一份顺时针转$90^{\circ }$,然后用三条单位线段将四分曲线按照左上-左下-右下-右上的顺序连接起来。如图所示,分别展示的是$H2$,$H3$,$H4$。加粗的线段是额外用于连接的线段。 灌水方式: (显然这个是$H3$的灌水面积)绿色即为无法被灌到的地方,红色为可以灌到的地方,灰色为墙,所以答案是$26$,即为样例1。 ![fuck](https://cdn.luogu.org/upload/pic/40229.png) 一个方格有水当且仅当在它的上,左,右方格中有至少一个方格有水,最上面一层的空格都有水。 注,此题要求对$9223372036854775783$取模

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

3

输出样例 #1

26

输入样例 #2

4

输出样例 #2

100

输入样例 #3

12

输出样例 #3

2137408

说明

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