#include using namespace std; typedef pair P; typedef long long ll; typedef vector vi; typedef vector vll; // #define int long long #define pb push_back #define mp make_pair #define eps 1e-9 #define INF 2000000000 //2e9 #define LLINF 1000000000000000ll // 1e15 #define fi first #define sec second #define all(x) (x).begin(),(x).end() #define sq(x) ((x)*(x)) #define dmp(x) cerr << #x << ": " << x << endl; template void chmin(T& a,const T& b){if(a>b)a=b;} template void chmax(T& a,const T& b){if(a using MaxHeap = priority_queue; template using MinHeap = priority_queue,greater>; template vector vect(int len,T elem){ return vector(len,elem); } template ostream& operator << (ostream& os,const pair& p){ os << p.fi << ',' << p.sec; return os; } template istream& operator >> (istream& is,pair& p){ is >> p.fi >> p.sec; return is; } template ostream& operator << (ostream &os,const vector &vec){ for(int i=0;i istream& operator >> (istream &is,vector& vec){ for(int i=0;i> vec[i]; return is; } void fastio(){ cin.tie(0); ios::sync_with_stdio(0); cout< // if inv is needed, this shold be prime. struct ModInt{ ll val; ModInt():val(0ll){} ModInt(const ll& v):val(((v%MOD)+MOD)%MOD){} bool operator==(const ModInt& x)const{return val==x.val;} bool operator!=(const ModInt& x)const{return !(*this==x);} bool operator<(const ModInt& x)const{return val(const ModInt& x)const{return val>x.val;} bool operator>=(const ModInt& x)const{return !(*thisx);} ModInt operator-()const{return ModInt(MOD-val);} ModInt inv()const{return this->pow(MOD-2);} ModInt& operator+=(const ModInt& x){if((val+=x.val)>=MOD)val-=MOD;return *this;} ModInt& operator-=(const ModInt& x){if((val+=MOD-x.val)>=MOD)val-=MOD;return *this;} ModInt& operator*=(const ModInt& x){(val*=x.val)%=MOD;return *this;} ModInt& operator/=(const ModInt& x){return *this *= x.inv();}; ModInt operator+(const ModInt& x)const{return ModInt(*this)+=x;} ModInt operator-(const ModInt& x)const{return ModInt(*this)-=x;} ModInt operator*(const ModInt& x)const{return ModInt(*this)*=x;} ModInt operator/(const ModInt& x)const{return ModInt(*this)/=x;} friend istream& operator>>(istream&i,ModInt& x){ll v;i>>v;x=v;return i;} friend ostream& operator<<(ostream&o,const ModInt& x){o<>= 1; b *= b; } return res; } }; template ModInt pow(ModInt a,ll x){ ModInt res = ModInt(1ll); while(x){ if(x&1)res *= a; x >>= 1; a *= a; } return res; } constexpr int MOD = 1e9+7; // constexpr int MOD = 998244353; using mint = ModInt; vector inv,fac,facinv; // notice: 0C0 = 1 ModInt nCr(int n,int r){ assert(!(n int digit(T x){ int res = 0; while(x){ x /= T(10); res++; } return res; } } namespace DS{ template struct RangeSum{ vector vec; RangeSum(){} RangeSum(vector elems):vec(elems){ for(int i=1;ir)return T(0); if(l==0)return vec[r]; else return vec[r]-vec[l-1]; } }; template struct BIT{ int N; vector bit; BIT(int N):N(N){ bit = vector(N+1,T(0)); } void add(int i,T x){ i++; while(i<=N){ bit[i]+=x; i+=i&-i; } return; } T sum(int i){ i++; T res = T(0); while(i>0){ res+=bit[i]; i-=i&-i; } return res; } T sum(int l,int r){// [l,r] assert(l<=r); if(l==0)return sum(r); else return sum(r)-sum(l-1); } }; template struct SlideMin{ vector v; deque deq; SlideMin(vector &v):v(v){} void add(int id){ while(!deq.empty()&&v[deq.back()]>=v[id])deq.pop_back(); deq.push_back(id); } T get(int id){ // [id,added] while(!deq.empty()&&deq.front() struct SlideMax{ vector v; deque deq; SlideMax(vector &v):v(v){} void add(int id){ while(!deq.empty()&&v[deq.back()]<=v[id])deq.pop_back(); deq.push_back(id); } T get(int id){ // [id,added] while(!deq.empty()&&deq.front() struct LazySegmentTree{ using DMerger = function; using OMerger = function; using Applier = function; int length; D d_unit; O o_unit; vector seg; vector lazy; DMerger dm; OMerger om; Applier app; void lazy_evaluate(int k,int len){ if(lazy[k] == o_unit) return; if(len>1){ lazy[2*k+1] = om(lazy[2*k+1],lazy[k]); lazy[2*k+2] = om(lazy[2*k+2],lazy[k]); } seg[k] = app(seg[k],lazy[k],len); lazy[k] = o_unit; } void update(int a,int b,int k,int l,int r,O x){ lazy_evaluate(k,r-l); if(r<=a||b<=l)return; else if(a<=l&&r<=b){ lazy[k] = om(lazy[k],x); lazy_evaluate(k,r-l); }else{ update(a,b,k*2+1,l,(l+r)/2,x); update(a,b,k*2+2,(l+r)/2,r,x); seg[k] = dm(seg[k*2+1],seg[k*2+2]); } } void update(int a,int b,O x){ update(a,b,0,0,length,x); } D query(int a,int b,int k,int l,int r){ lazy_evaluate(k,r-l); if(r<=a||b<=l)return d_unit; else if(a<=l&&r<=b)return seg[k]; else{ D lch = query(a,b,k*2+1,l,(l+r)/2); D rch = query(a,b,k*2+2,(l+r)/2,r); return dm(lch,rch); } } D query(int a,int b){ return query(a,b,0,0,length); } LazySegmentTree(int n,D d_unit,O o_unit,DMerger dm,OMerger om,Applier app) :length(1),d_unit(d_unit),o_unit(o_unit),dm(dm),om(om),app(app) { while(length vec,D d_unit,O o_unit,DMerger dm,OMerger om,Applier app) :length(1),d_unit(d_unit),o_unit(o_unit),dm(dm),om(om),app(app) { while(length=0;i--)seg[i] = dm(seg[i*2+1],seg[i*2+2]); } }; // RangeAddRangeSum update : a[l,r) += c // verified https://atcoder.jp/contests/abc153/submissions/9866001 template LazySegmentTree RangeAddRangeSum(int size){ auto dm = [](T a,T b){return a+b;}; auto om = [](T a,T b){return a+b;}; auto app = [](T dat,T lz,int len){return dat+lz*T(len);}; return LazySegmentTree(size,0ll,0ll,dm,om,app); } template LazySegmentTree RangeAddRangeSum(vector vec){ auto dm = [](T a,T b){return a+b;}; auto om = [](T a,T b){return a+b;}; auto app = [](T dat,T lz,int len){return dat+lz*T(len);}; return LazySegmentTree(vec,0ll,0ll,dm,om,app); } // RangeAddRangeMin // NOT verified yet template LazySegmentTree RangeAddRangeMin(int size){ auto dm = [](T a,T b){return min(a,b);}; auto om = [](T a,T b){return a+b;}; auto app = [](T dat,T lz,int len){return dat+lz;}; return LazySegmentTree(size,0ll,0ll,dm,om,app); } template LazySegmentTree RangeAddRangeMin(vector vec){ auto dm = [](T a,T b){return min(a,b);}; auto om = [](T a,T b){return a+b;}; auto app = [](T dat,T lz,int len){return dat+lz;}; return LazySegmentTree(vec,0ll,0ll,dm,om,app); } // RangeAffineRangeSum update (l,r,(p,q)) : a[i] = p * a[i] + q { i in [l,r) } // verified https://judge.yosupo.jp/submission/3354 template LazySegmentTree> RangeAffineRangeSum(int size){ using f = pair; auto dm = [](T a,T b){return a+b;}; auto om = [](f a,f b){return f(b.fi*a.fi,b.fi*a.sec+b.sec);}; auto app = [](T dat,f lz,int len){return lz.fi*dat+lz.sec*T(len);}; return LazySegmentTree(size,T(0),f(T(1),T(0)),dm,om,app); } template LazySegmentTree> RangeAffineRangeSum(vector vec){ using f = pair; auto dm = [](T a,T b){return a+b;}; auto om = [](f a,f b){return f(b.fi*a.fi,b.fi*a.sec+b.sec);}; auto app = [](T dat,f lz,int len){return lz.fi*dat+lz.sec*T(len);}; return LazySegmentTree(vec,T(0),f(T(1),T(0)),dm,om,app); } } namespace Util{ template vector> runLength(vector v){ vector> res; for(int i=0;i void compress(vector &v){ sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); } } signed main(){ fastio(); using namespace Math; int p; cin >> p; vector b(2000000); b[4] = mint(1); for(int i=5;i<=2000000;i++){ b[i] = mint(2*p)*b[i-1] + (mint(2)-mint(p)*mint(p))*b[i-2] - mint(2*p)*b[i-3] - b[i-4]; } int Q; cin >> Q; for(int i=0;i> q; cout << b[q] << endl; } return 0; }