题目描述

你是一个刚学习抽象代数的学生，今天老师布置了一个思考题。给一个 $m$ 维超立方体，求它的对称群内元素的个数。由于元素个数可能会比较多，输出对 $10^9+7$ 取模后的数值。 定义：

1. 群：满足某些性质的集合。详情可见https://baike.baidu.com/item/对称群/1801431
2. 对称群：下面会给出例子。

输入格式

一个数据，表示维度 $m \; (0 \leq m \leq 5 × 10^6)$。

输出格式

一个数据，表示对称群内的元素，若没有则输出 $0$。

输入样例

2

输出样例

8

提示

二维平面上的正方形 $A_{1}A_{2}A_{3}A_{4}$ 的对称中心为 $O$，$4$ 条对称轴分别记作 $l_{1},l_{2},l_{3},l_{4}$。 旋转：用 $\sigma$ 表示绕点 $O$ 转角为 $\frac{\pi}{2}$ 的旋转，则 $\sigma^2,\sigma^3$ 分别表示绕点 $O$ 转角为 $\pi,\frac{3\pi}{2}$ 的旋转。 反射：用 $\tau_{i}$ 表示 $l_{i}$ 的反射，$i=1,2,3,4$。（可以理解为翻折） 恒等：用 $I$ 表示平面的恒等变换。 显然正方形 $A_{1}A_{2}A_{3}A_{4}$ 的对称群 $G$ 至少包含上述 $8$ 个元素：$I,\sigma,\sigma^2,\sigma^3,\tau_{1},\tau_{2},\tau_{3},\tau_{4}$。 可以证明，没有其他的元素了。