#include <queue>

#include <stack>

#include <cmath>

#include <cstdio>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define fi first

#define se second

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int maxn  = 1000 + 5;

const int maxm  = 100 + 5;

const int inf   = 0x3f3f3f3f;

const LL  mod   = 10000 + 7;//19260817

const double pi = acos(-1.0);

LL n, res;

LL fpow(LL a, LL n){

	LL ans = 1;

	while(n){

		if(n & 1) ans = ans * a % mod;

		a = a * a % mod;

		n >>= 1;

	}

	return ans;

}

int main(){

	int T;

	scanf("%d", &T);

	while(T--){

		scanf("%lld", &n);

		printf("%lld\n", (1LL * fpow(4, n - 1) % mod + fpow(2, n - 1) % mod) % mod);

	}

    return 0;

}

原文链接：https://blog.csdn.net/qq_43464645/article/details/95488472