题解

首先用计数原理计算出答案为$3^n-3×2^n+3$，然后使用快速幂

#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
using namespace std;

int t(int a,int b)
{
	return ((a%MOD)*(b%MOD))%MOD;
}
int p(int base,int power)
{
	if (power==0)
		return 1;
	if (power==1)
		return base%MOD;
	int ans;
	if (power%2==0)
	{
		int tmp=p(base,power/2);
		ans=t(tmp,tmp);
	}
	else
	{
		int tmp=p(base,power/2);
		ans=t(base,tmp);
		ans=t(ans,tmp);
	}
	return ans%MOD;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    int T,n;
    cin >> T;
    while (T--)
    {
    	cin >> n;
    	int p1=p(3,n),p2=t(3,p(2,n));
    	int p3=(p1-p2+MOD)%MOD;
    	cout << (p3+3)%MOD << endl;
	}
	return 0;
}