【超长篇！一篇文章讲懂生成函数！】【那些你可能忘记了的算法5】生成函数&例题&卷积-CSDN博客

1-G36 生成函数的应用

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL P = 10007;
LL qpow(LL a, LL b) {
    int res = 1;
    for (; b; b >>= 1, a = a * a % P)
        if (b & 1) res = (res * a) % P;
    return res;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        LL n;
        scanf("%lld", &n);
        LL ans = (qpow(4LL, n) + qpow(2LL, n + 1)) % P * qpow(4LL, P - 2) % P;
        printf("%lld\n", ans);
    }
    return 0;
}