## Editorial for Tribonacci

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#include <bits/stdc++.h>
const long long MOD = 1000000000000007ll;
using namespace std;

struct mat {
long long a[4][4];
} a, b;
int t, n;
long long F[5], T[5];

long long mul(long long a, long long b) {
long long c = 0;
while (b) {
if (b & 1) {
c += a;
if (c >= MOD) c -= MOD;
}
a += a; if (a >= MOD) a -= MOD;
b /= 2;
}
return c;
}

mat operator * (mat a, mat b) {
mat c;
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++) {
c.a[i][j] = 0;
for(int k = 0; k < 4; k++)
c.a[i][j] = (c.a[i][j] + mul(a.a[i][k], b.a[k][j])) % MOD;
}
return c;
}

mat POW(int p) {
if (p == 1) return a;
mat x = POW(p / 2);
x = x * x;
if (p & 1) x = x * a;
return x;
}

int main() {
scanf("%d", &t);
a.a[0][0] = a.a[0][1] = a.a[1][1] = a.a[1][2] = a.a[1][3] = a.a[2][1] = a.a[3][2] = 1;
F[1] = 1; F[2] = 3; F[3] = 6; T[1] = 1; T[2] = 2; T[3] = 3;
while (t--) {
scanf("%d", &n);
if (n <= 3) printf("%lld\n", F[n]);
else {
b = POW(n - 2);
printf("%lld\n", (F[2] * b.a[0][0] + T[3] * b.a[0][1] + T[2] * b.a[0][2] + T[1] * b.a[0][3]) % MOD);
}
}
return 0;
}


#### Code mẫu của skyvn97

#include<cassert>
#include<cstdio>
#include<iostream>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
typedef long long ll;
const ll mod=(ll)   1e15+7LL;
struct Number {
ll val;
Number() {
val=0;
}
Number(ll x) {
val=x%mod;
}
Number operator + (const Number &x) const {
return (Number(val+x.val));
}
Number operator * (const Number &x) const {
ll res=0;
ll k=x.val;
while (k>0) {
k>>=1;
}
return (Number(res));
}
};
ostream& operator << (ostream &str,const Number &x) {
return (str<<x.val);
}
struct Matrix {
int m,n;
Number d[7][7];
Matrix() {
m=n=0;
}
Matrix(int _m,int _n) {
m=_m;
n=_n;
REP(i,m) REP(j,n) d[i][j]=Number(0);
}
Matrix operator * (const Matrix &a) const {
int x=m;
int y=n;
int z=a.n;
Matrix res=Matrix(x,z);
REP(i,x) REP(j,y) REP(k,z) res.d[i][k]=res.d[i][k]+d[i][j]*a.d[j][k];
return (res);
}
Matrix operator ^ (ll k) const {
Matrix res=Matrix(n,n);
REP(i,n) REP(j,n) res.d[i][j]=Number(i==j);
Matrix mul=*this;
while (k>0) {
if (k&1) res=res*mul;
mul=mul*mul;
k>>=1;
}
return (res);
}
};
const int Mul[][4]={{0,0,1,1},{1,0,1,1},{0,1,1,1},{0,0,0,1}};
const int Fst[]={1,2,3,6};
if (x<=3) return (Number(x*(x+1)/2));
Matrix fst=Matrix(1,4);
Matrix mul=Matrix(4,4);
REP(i,4) fst.d[0][i]=Number(Fst[i]);
REP(i,4) REP(j,4) mul.d[i][j]=Number(Mul[i][j]);
return ((fst*(mul^(x-3))).d[0][3]);
}
void check(void) {
ll x[40];
ll sum=0;
FOR(i,1,3) x[i]=i;
FOR(i,1,10000) {
if (i>3) x[i%4]=(x[(i-1)%4]+x[(i-2)%4]+x[(i-3)%4])%mod;
sum=(sum+x[i%4])%mod;
}
}
inline ll nextlong(void) {
ll x;
cin>>x;
return (x);
}
int main(void) {
#ifndef ONLINE_JUDGE
check();
cerr<<"OK"<<endl;
#endif
ios::sync_with_stdio(false);