本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-02 07:42:24

思路：

我们发现对于长度为 $6$ 的 $C$，对应的 $A, B$ 本质都是相同的。

即当 $C=\texttt{001001}$ 时 $A = \texttt{010101}$ 而 $B = \texttt{101010}$。

$A$ 与 $B$ 的区别就是把前三个和后三个交换了一下，但是由于 $C$ 每三个都是相同的，所以每六个 $A,B$ 的贡献是一样的。

然后由于长度为 $3^n$，所以一共有 $3^{n-1}$ 个 $3$。由于 $3^{n-1}$ 一定为奇数，所以一共有 $\frac{3^{n-1}-1}{2}$ 个 $6$ 以及一个 $3$。

那么每个 $6$ 的贡献一定是 $3$，所以考虑多余的一个 $3$ 贡献是多少。

那么一定是 $\texttt{010}$ 贡献最少为 $1$。

然后按照上边说的写即可。

Code:

#include<bits\/stdc++.h>

using namespace std;

typedef long long ll;
int T;
ll n;

const int mod = 1e9 + 7;

ll power(ll a, ll b) {
	ll res = 1;
	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1) res = res * a % mod;

	return res;
}

signed main(){
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &n);
		if (n == 1) printf("1\n");
		else {
			printf("%lld\n", ((power(3, n - 1) - 1 + mod) % mod) * power(2, mod - 2) % mod * 3ll % mod + 1);
		}
	}
    return 0;
}