记录编号	601116	评测结果	AAAAAAAAAA
题目名称	3108.[GXOI/GZOI2019]逼死强迫症	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2025-06-02 17:59:01	内存使用	1.41 MiB

#include <cstdio>
#include <cstring>
typedef long long ll;
#define isdigit(ch) (ch >= '0' && ch <= '9')

template <typename T>
T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T>
void write(T x, char ed = '\n') {
  if (x < 0) x = -x, putchar('-');
  static int sta[64], top;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while(x);
  while(top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}

const ll MOD = 1e9 + 7;

struct Matrix {
  int n, m;
  ll a[10][10];
  Matrix() {
    memset(a, 0, sizeof a);
  }
  Matrix(int n, int m, bool flag = false) : n(n), m(m) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
        a[i][j] = 0;
      }
      if (flag) a[i][i] = 1;
    }
  }
  ll* operator [] (int val) {
    return a[val];
  }
};

Matrix operator * (Matrix x, Matrix y) {
  Matrix res(x.n, y.m);
  for (int k = 1; k <= x.m; ++k) {
    for (int i = 1; i <= x.n; ++i) {
      for (int j = 1; j <= y.m; ++j) {
        res[i][j] = (res[i][j] + x[i][k] * y[k][j]) % MOD;
      }
    }
  }
  return res;
}

Matrix kasumi(Matrix x, ll y) {
  Matrix res(x.n, x.m, true);
  while (y) {
    if (y & 1) res = res * x;
    y >>= 1;
    x = x * x;
  }
  return res;
}

int T;

int main() {
  freopen("obsession.in", "r", stdin);
  freopen("obsession.out", "w", stdout);
  T = read<int>();
  while (T--) {
    ll n = read<ll>();
    if (n < 3) {
      write(0);
      continue;
    }
    Matrix X(1, 5), A(5, 5);
    X[1][1] = 2, X[1][2] = 0, X[1][3] = 1, X[1][4] = 1, X[1][5] = 1;
    A[1][1] = 1, A[2][1] = 1, A[5][1] = 2, A[1][2] = 1, A[3][3] = 1, A[4][3] = 1, A[3][4] = 1, A[3][5] = 1, A[5][5] = 1;
    A[3][1] = 2;
    write((X * kasumi(A, n - 3))[1][1]);
  }
  return 0;
}