Block

  这是冬训的一道关于矩阵快速幂的题目，但我硬是想不出递推式，于是只好硬推公式(同时部分参考题解)

推导过程如下图：

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll mod=10007;
ll fpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        ll ans=((fpow(2,n-1)-1)*fpow(2,n-1)+fpow(2,n)+mod)%mod;
        cout<<ans<<endl;
    }
    return 0;
}