这是问题的简单版本。不同之处在于,在此版本中,没有已选择颜色的节点。
Theofanis 饿了,他想吃他最喜欢的食物,sheftalia。不过,他应该先完成作业。你能帮他解决这个问题吗?
您有一个由 $$$2^k - 1$$$ 节点组成的完美二叉树 - 一个二叉树,其中从 $$$1$$$ 到 $$$2^{k - 1} - 1$$$ 的所有顶点 $$$i$$$ 恰好有两个子节点:顶点 $$$2i$$$ 和 $$$2i + 1$$$。从 $$$2^{k - 1}$$$ 到 $$$2^k - 1$$$ 的顶点没有任何子节点。您想要使用 $$$6$$$ 魔方颜色(白色、绿色、红色、蓝色、橙色和黄色)为其顶点着色。
当所有边连接的节点的颜色都是魔方中相邻边的颜色时,我们称着色为好。
魔方图片及其 2D 地图。
更正式地说:
- 白色节点不能与白色和黄色节点相邻;
- 黄色节点不能与白色和黄色节点相邻;
- 绿色节点不能与绿色和蓝色节点相邻;
- 蓝色节点不能与绿色和蓝色节点相邻;
- 红色节点不能与红色和橙色节点相邻;
- 橙色节点不能与红色和橙色节点相邻;
您想要计算二叉树的良好着色数。如果至少一个节点用不同的颜色着色,则两种颜色被认为是不同的。
答案可能太大,因此输出对 $$$10^9+7$$$ 取模的答案。
输入
第一行也是唯一一行包含整数 $$$k$$$ ($$$1 \le k \le 60$$$) — 您需要着色的完美二叉树中的级别数。
输出
打印一个整数——不同颜色的数量以 $$$10^9+7$$$ 为模。
示例
输入 #1
3
输出 #1
24576
输入 #2
14
输出 #2
934234
注意
在下图中,您可以看到第一个示例的正确颜色之一。