程序如下
其实就是斐波那契的矩阵乘法啊。

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int P = 1e9 + 7;
struct Matrix {
    int h, w;
    int a[10][10];
    Matrix(int n, int m) {
        h = n, w = m;
        for (int i = 1; i <= h; ++ i) {
            for (int j = 1; j <= w; ++ j) {
                a[i][j] = 0;
            }
        }
    }
    Matrix operator * (Matrix b) {
        Matrix c(h, w);
        for (int i = 1; i <= h; ++ i) {
            for (int j = 1; j <= w; ++ j) {
                for (int k = 1; k <= w; ++ k) {
                    c.a[i][j] += a[i][k] * b.a[k][j];
                }
            }
        }
        return c;
    }

    Matrix operator % (int mod) {
        Matrix c(h, w);
        for (int i = 1; i <= h; ++ i) {
            for (int j = 1; j <= w; ++ j) {
                c.a[i][j] = a[i][j] % mod;
            }
        }
        return c;
    }
};

Matrix f(1, 2);
Matrix s(2, 2);
int n, mod, T;

Matrix qpow(Matrix a, int b) {
    Matrix c(2, 2);
    for (int i = 1; i <= 2; ++ i) c.a[i][i] = 1;
    while (b) {
        if (b & 1)
            c = c * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return c % P;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("4910.in", "r", stdin);
    freopen("4910.out", "w", stdout);
#endif
    scanf("%lld", &T);
    while (T --) {
        scanf("%lld", &n);
        f.a[1][1] = f.a[1][2] = 1;
        s.a[1][1] = 1, s.a[1][2] = 1;
        s.a[2][1] = 1, s.a[2][2] = 0;
        cout << ((f * qpow(s, n - 1) % P).a[1][1] + (f * qpow(s, n - 2) % P).a[1][2]) % P << endl;
    }    
    return 0;
}