SP4166 HS08FOUR - Four colors
题目描述
在一条直线上，给定一系列点：$P_1, P_2, \ldots, P_n$。我们希望用四种颜色：白色、黑色、红色和蓝色来为这些点染色。要求对于每三个连续的点，要么：
1. 这三个点的颜色各不相同；
2. 至少有一个点的颜色是白色。
输入格式
输入的第一行是一个整数 $T$，表示测试用例的数量（$T < 100000$）。接下来的每一行包含一个正整数 $n$，表示点的个数（$n < 1000000000$）。总共有 5 组输入数据。
输出格式
对于每个测试用例，输出这些点的所有可能着色方案的数量。由于结果可能非常大，输出时请对 $1000000007$ 取模。
**本翻译由 AI 自动生成**