#include #include #include #include #include #include #include
v; v.push_back(3); v.push_back(9); v.push_back(20); v.push_back(46); v.push_back(106); v.push_back(244); v.push_back(560); v.push_back(1286); v.push_back(2956); v.push_back(6794); int nCase; scanf("%d", &nCase); while(nCase--){ scanf("%lld", &n); printf("%lld\n",1LL * linear_seq::gao(v,n-1) % mod); }}