立体主义绘画 - 题目

这个问题提供了一个交互式网页工具，让你亲自测试绘画过程！

你有一个表示为 $2 \times n$ 网格的画布，以及一个与画布方格边长相同的立方体。你想要用这个立方体来绘制画布，因此你首先要将立方体的每个面涂上不同的颜色，如下图所示：

请注意，这种着色方式是固定的，例如，红色面必须始终与蓝色面相对，以此类推。

你将通过首先将立方体（选择任意面朝下）放置在画布的任意方格上来进行绘制。然后，你可以反复将立方体沿着当前接触画布的任意边“滚动”。每当立方体的一个面接触到画布的一个方格时，该方格就会被涂上与该面相同的颜色。例如，这里是你可能进行的 5 步操作序列：

经过这一系列移动后，画布看起来会是这样：

如果两种颜色混合，产生的颜色会非常难看，所以你不希望在绘画中使用它。因此，一旦你涂好了一个方格，就不允许以会导致该方格被涂上不同颜色的方式移动立方体。注意，将一个方格多次涂上相同的颜色是可以的，如上例中的红色方格所示。

你希望使画布尽可能丰富多彩，因此你不希望在绘画完成后留下任何白色方格。

在这些限制条件下，有多少种不同的绘画方式？如果两个绘画在画布上存在至少一个方格的颜色不同，则认为它们是不同的。由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

你可以通过以下网址使用网页工具来移动立方体并绘制画布：https://joedurie.github.io/cubist-painting-web-tool/

第一行包含一个整数 $t$ ($1 \le t \le 1000$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例包含一行，其中包含一个整数 $n$ ($1 \le n \le 10^{18}$)，表示画布的列数。

对于每个测试用例，输出一个整数，表示 $2 \times n$ 画布上不同的绘画方式数量，对 $10^9 + 7$ 取模。

7
1
2
3
4
5
1000
1000000000000000000

以下是第一个样例中 24 种可能的绘画方式：

QOJ.ac