#include using namespace std; //fast IO by yosupo struct Scanner { FILE* fp = nullptr; char line[(1 << 15) + 1]; size_t st = 0, ed = 0; void reread() { memmove(line, line + st, ed - st); ed -= st; st = 0; ed += fread(line + ed, 1, (1 << 15) - ed, fp); line[ed] = '\0'; } bool succ() { while (true) { if (st == ed) { reread(); if (st == ed) return false; } while (st != ed && isspace(line[st])) st++; if (st != ed) break; } if (ed - st <= 50) reread(); return true; } template ::value, int> = 0> bool read_single(T& ref) { if (!succ()) return false; while (true) { size_t sz = 0; while (st + sz < ed && !isspace(line[st + sz])) sz++; ref.append(line + st, sz); st += sz; if (!sz || st != ed) break; reread(); } return true; } template ::value, int> = 0> bool read_single(T& ref) { if (!succ()) return false; bool neg = false; if (line[st] == '-') { neg = true; st++; } ref = T(0); while (isdigit(line[st])) { ref = 10 * ref + (line[st++] - '0'); } if (neg) ref = -ref; return true; } template bool read_single(vector& ref) { for (auto& d : ref) { if (!read_single(d)) return false; } return true; } void read() {} template void read(H& h, T&... t) { bool f = read_single(h); assert(f); read(t...); } Scanner(FILE* _fp) : fp(_fp) {} }; struct Printer { public: template void write() {} template void write(const H& h, const T&... t) { if (F) write_single(' '); write_single(h); write(t...); } template void writeln(const T&... t) { write(t...); write_single('\n'); } Printer(FILE* _fp) : fp(_fp) {} ~Printer() { flush(); } private: static constexpr size_t SIZE = 1 << 15; FILE* fp; char line[SIZE], small[50]; size_t pos = 0; void flush() { fwrite(line, 1, pos, fp); pos = 0; } void write_single(const char& val) { if (pos == SIZE) flush(); line[pos++] = val; } template ::value, int> = 0> void write_single(T val) { if (pos > (1 << 15) - 50) flush(); if (val == 0) { write_single('0'); return; } if (val < 0) { write_single('-'); val = -val; // todo min } size_t len = 0; while (val) { small[len++] = char('0' + (val % 10)); val /= 10; } reverse(small, small + len); memcpy(line + pos, small, len); pos += len; } void write_single(const string& s) { for (char c : s) write_single(c); } void write_single(const char* s) { size_t len = strlen(s); for (size_t i = 0; i < len; i++) write_single(s[i]); } template void write_single(const vector& val) { auto n = val.size(); for (size_t i = 0; i < n; i++) { if (i) write_single(' '); write_single(val[i]); } } }; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "< void chmax(t&a,u b){if(a void chmin(t&a,u b){if(b using vc=vector; template using vvc=vc>; using pi=pair; using vi=vc; template ostream& operator<<(ostream& os,const pair& p){ return os<<"{"< ostream& operator<<(ostream& os,const vc& v){ os<<"{"; for(auto e:v)os< void dmpr(ostream&os,const T&t,const Args&... args){ os< ostream& operator<<(ostream&os,const array&a){ return os<(all(a)); } template void print_tuple(ostream&,const T&){ } template void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<(t); print_tuple(os,t); } template ostream& operator<<(ostream&os,const tuple&t){ os<<"{"; print_tuple<0,tuple,Args...>(os,t); return os<<"}"; } template void print(t x,int suc=1){ cout<>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } template void print(const vector&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } string readString(){ string s; cin>>s; return s; } template T sq(const T& t){ return t*t; } //#define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } int mask(int i){ return (int(1)< void mkuni(vc&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static random_device rd; static mt19937_64 gen(rd()); #endif return uniform_int_distribution(l, r)(gen); } template int lwb(const vc&v,const t&a){ return lower_bound(all(v),a)-v.bg; } using uint=unsigned; using ull=unsigned long long; struct modinfo{uint mod,root;}; template struct modular{ static constexpr uint const &mod=ref.mod; static modular root(){return modular(ref.root);} uint v; //modular(initializer_listls):v(*ls.bg){} modular(ll vv=0){s(vv%mod+mod);} modular& s(uint vv){ v=vv>=1; } return res; } modular inv()const{return pow(mod-2);} /*modular inv()const{ int x,y; int g=extgcd(v,mod,x,y); assert(g==1); if(x<0)x+=mod; return modular(x); }*/ friend modular operator+(int x,const modular&y){ return modular(x)+y; } friend modular operator-(int x,const modular&y){ return modular(x)-y; } friend modular operator*(int x,const modular&y){ return modular(x)*y; } friend modular operator/(int x,const modular&y){ return modular(x)/y; } friend ostream& operator<<(ostream&os,const modular&m){ return os<>(istream&is,modular&m){ ll x;is>>x; m=modular(x); return is; } bool operator<(const modular&r)const{return v&f,const bool inv){ const int n=f.size(); const mint root=inv?prim_root.inv():prim_root; vc g(n); for(int b=n/2;b>=1;b/=2){ mint w=root.pow((mint::base-1)/(n/b)),p=1; for(int i=0;i void inplace_fmt(vector&f,bool inv){ const int n=si(f); static const int L=23; static mint g[L],ig[L],p2[L]; if(g[0].v==0){ rep(i,L){ mint w=-mint::root().pow(((mint::mod-1)>>(i+2))*3); g[i]=w; ig[i]=w.inv(); p2[i]=mint(1<>=1){//input:[0,mod) rep(i,b){ uint x=f[i+b].v; f[i+b].v=f[i].v+mint::mod-x; f[i].v+=x; } } if(b>>=1){//input:[0,mod*2) mint p=1; for(int i=0,k=0;i>=1){//input:[0,mod*3) mint p=1; for(int i=0,k=0;i>=1){//input:[0,mod*4) mint p=1; for(int i=0,k=0;i // vc multiply(vc x,const vc&y,bool same=false){ // int n=si(x)+si(y)-1; // int s=1; // while(s z(s); // rep(i,si(y))z[i]=y[i]; // inplace_fmt(z,false); // rep(i,s)x[i]*=z[i]; // }else{ // rep(i,s)x[i]*=x[i]; // } // inplace_fmt(x,true);x.resize(n); // return x; // } //59501818244292734739283969=5.95*10^25 までの値を正しく計算 //最終的な列の大きさが 2^24 までなら動く //最終的な列の大きさが 2^20 以下のときは,下の 3 つの素数を使ったほうが速い(は?) //VERIFY: yosupo namespace arbitrary_convolution{ constexpr modinfo base0{167772161,3};//2^25 * 5 + 1 constexpr modinfo base1{469762049,3};//2^26 * 7 + 1 constexpr modinfo base2{754974721,11};//2^24 * 45 + 1 // constexpr modinfo base0{1045430273,3};//2^20 * 997 + 1 // constexpr modinfo base1{1051721729,6};//2^20 * 1003 + 1 // constexpr modinfo base2{1053818881,7};//2^20 * 1005 + 1 using mint0=modular; using mint1=modular; using mint2=modular; template vc sub(const vc&x,const vc&y,bool same=false){ int n=si(x)+si(y)-1; int s=1; while(s z(s);rep(i,si(x))z[i]=x[i].v; inplace_fmt(z,false); if(!same){ vc w(s);rep(i,si(y))w[i]=y[i].v; inplace_fmt(w,false); rep(i,s)z[i]*=w[i]; }else{ rep(i,s)z[i]*=z[i]; } inplace_fmt(z,true);z.resize(n); return z; } template vc multiply(const vc&x,const vc&y,bool same=false){ auto d0=sub(x,y,same); auto d1=sub(x,y,same); auto d2=sub(x,y,same); int n=si(d0); vc res(n); static const mint1 r01=mint1(mint0::mod).inv(); static const mint2 r02=mint2(mint0::mod).inv(); static const mint2 r12=mint2(mint1::mod).inv(); static const mint2 r02r12=r02*r12; static const mint w1=mint(mint0::mod); static const mint w2=w1*mint(mint1::mod); rep(i,n){ ull a=d0[i].v; ull b=(d1[i].v+mint1::mod-a)*r01.v%mint1::mod; ull c=((d2[i].v+mint2::mod-a)*r02r12.v+(mint2::mod-b)*r12.v)%mint2::mod; res[i].v=(a+b*w1.v+c*w2.v)%mint::mod; } return res; } } using arbitrary_convolution::multiply; //constexpr modinfo base{998244353,3}; constexpr modinfo base{1000000007,0}; using mint=modular; signed main(){ //cin.tie(0); //ios::sync_with_stdio(0); //cout< a(m+1); a[0] = a[1] = 0; a[2] = 1; rng(i, 3, m+1) a[i] = ((ll)a[i-1]*p%mo + a[i-2]) % mo; // rep(i, 10) { // pr.write(a[i]); // pr.write(' '); // } // pr.write('\n'); vc b(m+1); rep(i, m+1) b[i].v = a[i]; auto c = multiply(b, b, true); // rep(i, 10) { // pr.write(c[i].v); // pr.write(' '); // } // pr.write('\n'); int q; sc.read(q); rep(i,q){ int x; sc.read(x); pr.write(c[x].v); pr.write('\n'); } // Scanner sc(stdin); // Printer pr(stdout); // int n, m; // cin >> n >> m; // vc a(n),b(m); // rep(i,n) cin >> a[i].v; // rep(i,m) cin >> b[i].v; // auto c=multiply(a,b); // cout << c << endl; // rep(i,c.size()){ // pr.write(c[i].v); // pr.write(i