思路：

递推 + 快速幂优化。

实现：

1 #include 
     
       2 #include 
      
        3 #include 
       
          4 using namespace std; 5 typedef vector
        
         
           > matrix; 6  7 const int MOD = 10007; 8  9 matrix multiply(matrix & a, matrix & b)10 {11     matrix c(a.size(), vector
          
           (b[0].size()));12 for (int i = 0; i < a.size(); i++)13 {14 for (int k = 0; k < a[0].size(); k++)15 {16 for (int j = 0; j < b[0].size(); j++)17 {18 c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;19 }20 }21 }22 return c;23 }24 25 matrix pow(matrix & a, long long n)26 {27 matrix res(a.size(), vector
           
            (a[0].size()));28 for (int i = 0; i < a.size(); i++)29 {30 res[i][i] = 1;31 }32 while (n > 0)33 {34 if (n & 1)35 res = multiply(res, a);36 a = multiply(a, a);37 n >>= 1;38 }39 return res;40 }41 int main()42 {43 int t;44 long long n;45 cin >> t;46 while (t--)47 {48 scanf("%lld", &n);49 matrix a(3, vector
            
             (3));50 a[0][0] = 2; a[0][1] = 1; 51 a[1][0] = 2; a[1][1] = 2; a[1][2] = 2;52 a[2][1] = 1; a[2][2] = 2;53 a = pow(a, n);54 matrix b(3, vector
             
              (1));55 b[0][0] = 1;56 b[1][0] = 0;57 b[2][0] = 0;58 a = multiply(a, b);59 cout << a[0][0] << endl;60 }61 return 0; 62 }