POJ3734 Blocks(生成函数)

#include<iostream>
#include<cstdio>
using namespace std;
const int mod = 10007;
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = 1ll * base * a % mod;
        a = 1ll * a * a % mod; p >>= 1;
    }
    return base;
}
void solve() {
    int n; cin >> n;
    cout << 1ll * (fp(4, n) + 2ll * fp(2, n) % mod) % mod * fp(4, mod - 2) % mod << '\n';
}
int main() {
    int T; cin >> T;
    for(; T--; solve());
    return 0;
}