//#define _GLIBCXX_DEBUG //#pragma GCC target("avx2") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug_print.hpp> #define OUT(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else #define OUT(...) (static_cast<void>(0)) #endif #define endl '\n' #define lfs cout<<fixed<<setprecision(15) #define ALL(a) (a).begin(),(a).end() #define ALLR(a) (a).rbegin(),(a).rend() #define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end()) #define spa << " " << #define fi first #define se second #define MP make_pair #define MT make_tuple #define PB push_back #define EB emplace_back #define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++) #define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--) namespace template_tute{ using ll = long long; using ld = long double; const ll MOD1 = 1e9+7; const ll MOD9 = 998244353; const ll INF = 4.1e18; using P = pair<ll, ll>; template<typename T> using PQ = priority_queue<T>; template<typename T> using QP = priority_queue<T,vector<T>,greater<T>>; template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;} template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;} ll median(ll a,ll b, ll c){return a+b+c-max<ll>({a,b,c})-min<ll>({a,b,c});} void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;} void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;} void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;} template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;} template<typename T1,typename T2,typename T3>void anss(T1 x,T2 y,T3 z){ans(x!=y,x,z);}; template<typename T>void debug(const T &v,ll h,ll w,string sv=" "){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout<<sv<<v[i][j];cout<<endl;}}; template<typename T>void debug(const T &v,ll n,string sv=" "){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout<<sv<<v[i];cout<<endl;}; template<typename T>void debug(const vector<T>&v){debug(v,v.size());} template<typename T>void debug(const vector<vector<T>>&v){for(auto &vv:v)debug(vv,vv.size());} template<typename T>void debug(stack<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;} template<typename T>void debug(queue<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop();}cout<<endl;} template<typename T>void debug(deque<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop_front();}cout<<endl;} template<typename T>void debug(PQ<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;} template<typename T>void debug(QP<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;} template<typename T>void debug(const set<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;} template<typename T>void debug(const multiset<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;} template<typename T,size_t size>void debug(const array<T, size> &a){for(auto z:a)cout<<z<<" ";cout<<endl;} template<typename T,typename V>void debug(const map<T,V>&v){for(auto z:v)cout<<"["<<z.first<<"]="<<z.second<<",";cout<<endl;} template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;} vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1}; template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);} template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));} template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << "(" << p.first << "," << p.second << ")";} template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){os<<"[";for(auto &z:v)os << z << ",";os<<"]"; return os;} template<typename T>void rearrange(vector<int>&ord, vector<T>&v){ auto tmp = v; for(int i=0;i<tmp.size();i++)v[i] = tmp[ord[i]]; } template<typename Head, typename... Tail>void rearrange(vector<int>&ord,Head&& head, Tail&&... tail){ rearrange(ord, head); rearrange(ord, tail...); } template<typename T> vector<int> ascend(const vector<T>&v){ vector<int>ord(v.size());iota(ord.begin(),ord.end(),0); sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],i)<make_pair(v[j],j);}); return ord; } template<typename T> vector<int> descend(const vector<T>&v){ vector<int>ord(v.size());iota(ord.begin(),ord.end(),0); sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],-i)>make_pair(v[j],-j);}); return ord; } template<typename T> vector<T> inv_perm(const vector<T>&ord){ vector<T>inv(ord.size()); for(int i=0;i<ord.size();i++)inv[ord[i]] = i; return inv; } ll FLOOR(ll n,ll div){assert(div>0);return n>=0?n/div:(n-div+1)/div;} ll CEIL(ll n,ll div){assert(div>0);return n>=0?(n+div-1)/div:n/div;} ll digitsum(ll n){ll ret=0;while(n){ret+=n%10;n/=10;}return ret;} ll modulo(ll n,ll d){return (n%d+d)%d;}; template<typename T>T min(const vector<T>&v){return *min_element(v.begin(),v.end());} template<typename T>T max(const vector<T>&v){return *max_element(v.begin(),v.end());} template<typename T>T acc(const vector<T>&v){return accumulate(v.begin(),v.end(),T(0));}; template<typename T>T reverse(const T &v){return T(v.rbegin(),v.rend());}; //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); int popcount(ll x){return __builtin_popcountll(x);}; int poplow(ll x){return __builtin_ctzll(x);}; int pophigh(ll x){return 63 - __builtin_clzll(x);}; template<typename T>T poll(queue<T> &q){auto ret=q.front();q.pop();return ret;}; template<typename T>T poll(priority_queue<T> &q){auto ret=q.top();q.pop();return ret;}; template<typename T>T poll(QP<T> &q){auto ret=q.top();q.pop();return ret;}; template<typename T>T poll(stack<T> &s){auto ret=s.top();s.pop();return ret;}; ll MULT(ll x,ll y){if(LLONG_MAX/x<=y)return LLONG_MAX;return x*y;} ll POW2(ll x, ll k){ll ret=1,mul=x;while(k){if(mul==LLONG_MAX)return LLONG_MAX;if(k&1)ret=MULT(ret,mul);mul=MULT(mul,mul);k>>=1;}return ret;} ll POW(ll x, ll k){ll ret=1;for(int i=0;i<k;i++){if(LLONG_MAX/x<=ret)return LLONG_MAX;ret*=x;}return ret;} std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } namespace converter{ int dict[500]; const string lower="abcdefghijklmnopqrstuvwxyz"; const string upper="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string digit="0123456789"; const string digit1="123456789"; void regi_str(const string &t){ for(int i=0;i<t.size();i++){ dict[t[i]]=i; } } void regi_int(const string &t){ for(int i=0;i<t.size();i++){ dict[i]=t[i]; } } vector<int>to_int(const string &s,const string &t){ regi_str(t); vector<int>ret(s.size()); for(int i=0;i<s.size();i++){ ret[i]=dict[s[i]]; } return ret; } vector<int>to_int(const string &s){ auto t=s; sort(t.begin(),t.end()); t.erase(unique(t.begin(),t.end()),t.end()); return to_int(s,t); } vector<vector<int>>to_int(const vector<string>&s,const string &t){ regi_str(t); vector<vector<int>>ret(s.size(),vector<int>(s[0].size())); for(int i=0;i<s.size();i++){ for(int j=0;j<s[0].size();j++){ ret[i][j]=dict[s[i][j]]; } } return ret; } vector<vector<int>>to_int(const vector<string>&s){ string t; for(int i=0;i<s.size();i++){ t+=s[i]; } sort(t.begin(),t.end());t.erase(unique(t.begin(),t.end()),t.end()); return to_int(s,t); } string to_str(const vector<int>&s,const string &t){ regi_int(t); string ret; for(auto z:s)ret+=dict[z]; return ret; } vector<string> to_str(const vector<vector<int>>&s,const string &t){ regi_int(t); vector<string>ret(s.size()); for(int i=0;i<s.size();i++){ for(auto z:s[i])ret[i]+=dict[z]; } return ret; } } template< typename T = int > struct edge { int to; T cost; int id; edge():to(-1),id(-1){}; edge(int to, T cost = 1, int id = -1):to(to), cost(cost), id(id){} operator int() const { return to; } }; template<typename T> using Graph = vector<vector<edge<T>>>; template<typename T> Graph<T>revgraph(const Graph<T> &g){ Graph<T>ret(g.size()); for(int i=0;i<g.size();i++){ for(auto e:g[i]){ int to = e.to; e.to = i; ret[to].push_back(e); } } return ret; } template<typename T> Graph<T> readGraph(int n,int m,int indexed=1,bool directed=false,bool weighted=false){ Graph<T> ret(n); for(int es = 0; es < m; es++){ int u,v; T w=1; cin>>u>>v;u-=indexed,v-=indexed; if(weighted)cin>>w; ret[u].emplace_back(v,w,es); if(!directed)ret[v].emplace_back(u,w,es); } return ret; } template<typename T> Graph<T> readParent(int n,int indexed=1,bool directed=true){ Graph<T>ret(n); for(int i=1;i<n;i++){ int p;cin>>p; p-=indexed; ret[p].emplace_back(i); if(!directed)ret[i].emplace_back(p); } return ret; } } using namespace template_tute; template< int mod > struct ModInt { int x; ModInt() : x(0) {} ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} ModInt &operator+=(const ModInt &p) { if((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int) (1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } friend ModInt operator+(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) += rhs; } friend ModInt operator-(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) -= rhs; } friend ModInt operator*(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) *= rhs; } friend ModInt operator/(const ModInt& lhs, const ModInt& rhs) { return ModInt(lhs) /= rhs; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(int64_t n) const { ModInt ret(1), mul(x); while(n > 0) { if(n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } pair<int,int>frac(){ for(int j=1;j<=10000;j++){ auto v=*this*j; if(v.x<=10000)return make_pair(v.x,j); else if(v.x>=mod-10000)return make_pair(-(v.x-mod),j); } return make_pair(-1,-1); } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt< mod >(t); return (is); } static constexpr int get_mod() { return mod; } }; template< typename T > struct Combination { vector< T > _fact, _rfact, _inv; Combination(ll sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) { _fact[0] = _rfact[sz] = _inv[0] = 1; for(ll i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i; _rfact[sz] /= _fact[sz]; for(ll i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1); for(ll i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1]; } inline T fact(ll k) const { return _fact[k]; } inline T rfact(ll k) const { return _rfact[k]; } inline T inv(ll k) const { return _inv[k]; } T P(ll n, ll r) const { if(r < 0 || n < r) return 0; return fact(n) * rfact(n - r); } T C(ll p, ll q) const { if(q < 0 || p < q) return 0; return fact(p) * rfact(q) * rfact(p - q); } T RC(ll p, ll q) const { if(q < 0 || p < q) return 0; return rfact(p) * fact(q) * fact(p - q); } T H(ll n, ll r) const { if(n < 0 || r < 0) return (0); return r == 0 ? 1 : C(n + r - 1, r); } //+1がm個、-1がn個で prefix sumが常にk以上 T catalan(ll m,ll n,ll k){ if(n>m-k)return 0; else return C(n+m,m)-C(n+m,n+k-1); } }; using modint = ModInt< MOD9 >;modint mpow(ll n, ll x){return modint(n).pow(x);}modint mpow(modint n, ll x){return n.pow(x);} //using modint=ld;modint mpow(ll n, ll x){return pow(n,x);}modint mpow(modint n, ll x){return pow(n,x);} using Comb=Combination<modint>; template< typename Mint > struct NumberTheoreticTransformFriendlyModInt { static constexpr uint32_t get_pr() { uint32_t _mod = Mint::get_mod(); using u64 = uint64_t; u64 ds[32] = {}; int idx = 0; u64 m = _mod - 1; for (u64 i = 2; i * i <= m; ++i) { if (m % i == 0) { ds[idx++] = i; while (m % i == 0) m /= i; } } if (m != 1) ds[idx++] = m; uint32_t _pr = 2; while (1) { int flg = 1; for (int i = 0; i < idx; ++i) { u64 a = _pr, b = (_mod - 1) / ds[i], r = 1; while (b) { if (b & 1) r = r * a % _mod; a = a * a % _mod; b >>= 1; } if (r == 1) { flg = 0; break; } } if (flg == 1) break; ++_pr; } return _pr; }; static constexpr uint32_t root = get_pr(); static vector< Mint > dw, idw; NumberTheoreticTransformFriendlyModInt() = default; static void init() { dw.resize(level); idw.resize(level); setwy(level); } static void fft4(vector<Mint> &a, int k) { if ((int)a.size() <= 1) return; if (k == 1) { Mint a1 = a[1]; a[1] = a[0] - a[1]; a[0] = a[0] + a1; return; } if (k & 1) { int v = 1 << (k - 1); for (int j = 0; j < v; ++j) { Mint ajv = a[j + v]; a[j + v] = a[j] - ajv; a[j] += ajv; } } int u = 1 << (2 + (k & 1)); int v = 1 << (k - 2 - (k & 1)); Mint one = Mint(1); Mint imag = dw[1]; while (v) { // jh = 0 { int j0 = 0; int j1 = v; int j2 = j1 + v; int j3 = j2 + v; for (; j0 < v; ++j0, ++j1, ++j2, ++j3) { Mint t0 = a[j0], t1 = a[j1], t2 = a[j2], t3 = a[j3]; Mint t0p2 = t0 + t2, t1p3 = t1 + t3; Mint t0m2 = t0 - t2, t1m3 = (t1 - t3) * imag; a[j0] = t0p2 + t1p3, a[j1] = t0p2 - t1p3; a[j2] = t0m2 + t1m3, a[j3] = t0m2 - t1m3; } } // jh >= 1 Mint ww = one, xx = one * dw[2], wx = one; for (int jh = 4; jh < u;) { ww = xx * xx, wx = ww * xx; int j0 = jh * v; int je = j0 + v; int j2 = je + v; for (; j0 < je; ++j0, ++j2) { Mint t0 = a[j0], t1 = a[j0 + v] * xx, t2 = a[j2] * ww, t3 = a[j2 + v] * wx; Mint t0p2 = t0 + t2, t1p3 = t1 + t3; Mint t0m2 = t0 - t2, t1m3 = (t1 - t3) * imag; a[j0] = t0p2 + t1p3, a[j0 + v] = t0p2 - t1p3; a[j2] = t0m2 + t1m3, a[j2 + v] = t0m2 - t1m3; } xx *= dw[__builtin_ctzll((jh += 4))]; } u <<= 2; v >>= 2; } } static void ifft4(vector<Mint> &a, int k) { if ((int)a.size() <= 1) return; if (k == 1) { Mint a1 = a[1]; a[1] = a[0] - a[1]; a[0] = a[0] + a1; return; } int u = 1 << (k - 2); int v = 1; Mint one = Mint(1); Mint imag = idw[1]; while (u) { // jh = 0 { int j0 = 0; int j1 = v; int j2 = v + v; int j3 = j2 + v; for (; j0 < v; ++j0, ++j1, ++j2, ++j3) { Mint t0 = a[j0], t1 = a[j1], t2 = a[j2], t3 = a[j3]; Mint t0p1 = t0 + t1, t2p3 = t2 + t3; Mint t0m1 = t0 - t1, t2m3 = (t2 - t3) * imag; a[j0] = t0p1 + t2p3, a[j2] = t0p1 - t2p3; a[j1] = t0m1 + t2m3, a[j3] = t0m1 - t2m3; } } // jh >= 1 Mint ww = one, xx = one * idw[2], yy = one; u <<= 2; for (int jh = 4; jh < u;) { ww = xx * xx, yy = xx * imag; int j0 = jh * v; int je = j0 + v; int j2 = je + v; for (; j0 < je; ++j0, ++j2) { Mint t0 = a[j0], t1 = a[j0 + v], t2 = a[j2], t3 = a[j2 + v]; Mint t0p1 = t0 + t1, t2p3 = t2 + t3; Mint t0m1 = (t0 - t1) * xx, t2m3 = (t2 - t3) * yy; a[j0] = t0p1 + t2p3, a[j2] = (t0p1 - t2p3) * ww; a[j0 + v] = t0m1 + t2m3, a[j2 + v] = (t0m1 - t2m3) * ww; } xx *= idw[__builtin_ctzll(jh += 4)]; } u >>= 4; v <<= 2; } if (k & 1) { u = 1 << (k - 1); for (int j = 0; j < u; ++j) { Mint ajv = a[j] - a[j + u]; a[j] += a[j + u]; a[j + u] = ajv; } } } static void ntt(vector<Mint> &a) { if ((int)a.size() <= 1) return; fft4(a, __builtin_ctz(a.size())); } static void intt(vector<Mint> &a) { if ((int)a.size() <= 1) return; ifft4(a, __builtin_ctz(a.size())); Mint iv = Mint(a.size()).inverse(); for (auto &x : a) x *= iv; } static constexpr int mod = Mint::get_mod(); static constexpr int level = __builtin_ctzll(mod - 1); static void setwy(int k) { Mint w[level], y[level]; w[k - 1] = Mint(root).pow((mod - 1) / (1 << k)); y[k - 1] = w[k - 1].inverse(); for (int i = k - 2; i > 0; --i) w[i] = w[i + 1] * w[i + 1], y[i] = y[i + 1] * y[i + 1]; dw[1] = w[1], idw[1] = y[1], dw[2] = w[2], idw[2] = y[2]; for (int i = 3; i < k; ++i) { dw[i] = dw[i - 1] * y[i - 2] * w[i]; idw[i] = idw[i - 1] * w[i - 2] * y[i]; } } static vector<Mint> multiply(const vector<Mint> &a, const vector<Mint> &b) { int l = a.size() + b.size() - 1; if (min<int>(a.size(), b.size()) <= 40) { vector<Mint> s(l); for (int i = 0; i < (int)a.size(); ++i) for (int j = 0; j < (int)b.size(); ++j) s[i + j] += a[i] * b[j]; return s; } int k = 2, M = 4; while (M < l) M <<= 1, ++k; setwy(k); vector<Mint> s(M); for (int i = 0; i < (int)a.size(); ++i) s[i] = a[i]; fft4(s, k); if (a.size() == b.size() && a == b) { for (int i = 0; i < M; ++i) s[i] *= s[i]; } else { vector<Mint> t(M); for (int i = 0; i < (int)b.size(); ++i) t[i] = b[i]; fft4(t, k); for (int i = 0; i < M; ++i) s[i] *= t[i]; } ifft4(s, k); s.resize(l); Mint invm = Mint(M).inverse(); for (int i = 0; i < l; ++i) s[i] *= invm; return s; } static void ntt_doubling(vector<Mint> &a) { int M = (int)a.size(); auto b = a; intt(b); Mint r = 1, zeta = Mint(root).pow((Mint::get_mod() - 1) / (M << 1)); for (int i = 0; i < M; i++) b[i] *= r, r *= zeta; ntt(b); copy(begin(b), end(b), back_inserter(a)); } }; template< typename Mint > vector< Mint > NumberTheoreticTransformFriendlyModInt<Mint>::dw = vector< Mint >(); template< typename Mint > vector< Mint > NumberTheoreticTransformFriendlyModInt< Mint >::idw = vector< Mint >(); //ret[i-j]=x[i]*y[j] template<typename Conv, typename T> vector<T>multiply_minus(vector<T>x,vector<T>y){ reverse(y.begin(),y.end()); auto tmp = Conv::multiply(x,y); vector<T>ret(x.size()); for(int i = 0; i < x.size(); i++){ ret[i] = tmp[y.size() - 1 + i]; } return ret; } // void solve(){ ll res=0,buf=0; bool judge = true; NumberTheoreticTransformFriendlyModInt<modint>::init(); ll n,q;cin>>n>>q; vector<modint>a(n); rep(i,0,n)cin>>a[i]; while(q--){ ll t;cin>>t; if(t==1){ ll k,x;cin>>k>>x; vector<modint>b(n+1,1); rep(i,0,n+1){ b[i+1]=b[i]*(x+i)/(i+1)*k; } a=NumberTheoreticTransformFriendlyModInt<modint>::multiply(a,b); a.resize(n); } else{ ll x;cin>>x;x--; cout<<a[x]<<endl; } } } int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll res=0,buf=0; bool judge = true; int T = 1; //cin>>T; while(T--){ solve(); } return 0; }