#include #include #include #include #include #include #include #include #include #include #include #include #define vll vector #define vvvl vector #define vvl vector> #define VV(a, b, c, d) vector>(a, vector(b, c)) #define VVV(a, b, c, d) vector(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c (集合, 加法における単位元, 加算, 乗算) template struct matrix{ function f, g; vector> mat; T unit; matrix(vector> v, T UNIT, function add_func, function multi_func):f(add_func), g(multi_func), unit(UNIT){ mat = v; } matrix t(){ vector> ret(mat[0].size(), vector(mat.size())); re(i, mat[0].size()) re(j, mat.size()) ret[i][j] = mat[j][i]; return matrix(ret, f, g); } matrix operator * (matrix B){ vector> ret(mat.size(), vector(B.mat[0].size(), unit)); if(mat[0].size()!=B.mat.size()){ std::cout << "matrix operator " << "*" << " error" << '\n'; return matrix(ret, unit, f, g); } re(i, mat.size()){ re(j, B.mat[0].size()){ re(k, mat[0].size()){ ret[i][j] = f(ret[i][j], g(mat[i][k], B.mat[k][j])); } } } return matrix(ret, unit, f, g); } matrix operator * (ll num){ vector> ret = mat; re(i, mat.size()) re(j, mat[0].size()) ret[i][j] *= num; return matrix(ret, unit, f, g); } matrix operator + (matrix B){ vector> ret = mat; if(mat.size()!=B.mat.size()||mat[0].size()!=B.mat[0].size()){ std::cout << "matrix operator " << "+" << " error" << '\n'; return matrix(ret, unit, f, g); } re(i, mat.size()) re(j, mat[0].size()) ret[i][j] = f(mat[i][j], B.mat[i][j]); return matrix(ret, unit, f, g); } matrix operator ^ (ll num){ matrix ret(vector> (0, vector(0)), unit, f, g); if(mat.size()!=mat[0].size()){ std::cout << "matrix operator " << "^" << " error" << '\n'; return ret; } matrix tmp(mat, unit, f, g); bool flag = false; while(num>0){ if(num%2){ if(flag) ret = ret * tmp; else ret.mat = tmp.mat, flag = true; } num/=2, tmp = tmp * tmp; } return ret; } vector & operator [](int n){ return mat[n]; } }; #define P 17 ll ad(ll a, ll b){return (a+b)%P;} ll ml(ll a, ll b){return (a*b)%P;} int main() { matrix A({{1},{0},{0},{0}}, 0, ad, ml); matrix B({{1, 1, 1, 1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}, 0, ad, ml); ll q;std::cin >> q; re(i, q){ ll t;std::cin >> t; if(t<=3) std::cout << 0 << '\n'; if(t==4) std::cout << 1 << '\n'; if(t>4){ matrix C = (B^(t-4))*A; std::cout << C[0][0] << '\n'; } } }