#define PROBLEM "https://judge.yosupo.jp/problem/polynomial_interpolation"
//#include"../../template/template.hpp"//#include"../../fps/fast-interpolate.hpp"
#include"../../fps/ntt-friendly-fps.hpp"
#include"../../modint/montgomery-modint.hpp"// #include "fps/arbitrary-fps.hpp"//usingnamespaceNyaan;usingmint=LazyMontgomeryModInt<998244353>;// using mint = LazyMontgomeryModInt<1000000007>;usingvm=vector<mint>;usingvvm=vector<vm>;usingfps=FormalPowerSeries<mint>;usingnamespaceNyaan;voidq(){ini(N);vmx(N),y(N);in(x,y);SubproductTreest{x};out(st.interpolate(y));}voidNyaan::solve(){intt=1;// in(t);while(t--)q();}
#line 1 "verify/verify-yosupo-fps/yosupo-polynomial-interpolation-fast.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/polynomial_interpolation"
//#line 2 "template/template.hpp"
usingnamespacestd;// intrinstic#include<immintrin.h>#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cfenv>
#include<cfloat>
#include<chrono>
#include<cinttypes>
#include<climits>
#include<cmath>
#include<complex>
#include<cstdarg>
#include<cstddef>
#include<cstdint>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<deque>
#include<fstream>
#include<functional>
#include<initializer_list>
#include<iomanip>
#include<ios>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<stack>
#include<streambuf>
#include<string>
#include<tuple>
#include<type_traits>
#include<typeinfo>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>// utility#line 1 "template/util.hpp"
namespaceNyaan{usingll=longlong;usingi64=longlong;usingu64=unsignedlonglong;usingi128=__int128_t;usingu128=__uint128_t;template<typenameT>usingV=vector<T>;template<typenameT>usingVV=vector<vector<T>>;usingvi=vector<int>;usingvl=vector<longlong>;usingvd=V<double>;usingvs=V<string>;usingvvi=vector<vector<int>>;usingvvl=vector<vector<longlong>>;template<typenameT>usingminpq=priority_queue<T,vector<T>,greater<T>>;template<typenameT,typenameU>structP:pair<T,U>{template<typename...Args>P(Args...args):pair<T,U>(args...){}usingpair<T,U>::first;usingpair<T,U>::second;P&operator+=(constP&r){first+=r.first;second+=r.second;return*this;}P&operator-=(constP&r){first-=r.first;second-=r.second;return*this;}P&operator*=(constP&r){first*=r.first;second*=r.second;return*this;}template<typenameS>P&operator*=(constS&r){first*=r,second*=r;return*this;}Poperator+(constP&r)const{returnP(*this)+=r;}Poperator-(constP&r)const{returnP(*this)-=r;}Poperator*(constP&r)const{returnP(*this)*=r;}template<typenameS>Poperator*(constS&r)const{returnP(*this)*=r;}Poperator-()const{returnP{-first,-second};}};usingpl=P<ll,ll>;usingpi=P<int,int>;usingvp=V<pl>;constexprintinf=1001001001;constexprlonglonginfLL=4004004004004004004LL;template<typenameT>intsz(constT&t){returnt.size();}template<typenameT,typenameU>inlineboolamin(T&x,Uy){return(y<x)?(x=y,true):false;}template<typenameT,typenameU>inlineboolamax(T&x,Uy){return(x<y)?(x=y,true):false;}template<typenameT>inlineTMax(constvector<T>&v){return*max_element(begin(v),end(v));}template<typenameT>inlineTMin(constvector<T>&v){return*min_element(begin(v),end(v));}template<typenameT>inlinelonglongSum(constvector<T>&v){returnaccumulate(begin(v),end(v),0LL);}template<typenameT>intlb(constvector<T>&v,constT&a){returnlower_bound(begin(v),end(v),a)-begin(v);}template<typenameT>intub(constvector<T>&v,constT&a){returnupper_bound(begin(v),end(v),a)-begin(v);}constexprlonglongTEN(intn){longlongret=1,x=10;for(;n;x*=x,n>>=1)ret*=(n&1?x:1);returnret;}template<typenameT,typenameU>pair<T,U>mkp(constT&t,constU&u){returnmake_pair(t,u);}template<typenameT>vector<T>mkrui(constvector<T>&v,boolrev=false){vector<T>ret(v.size()+1);if(rev){for(inti=int(v.size())-1;i>=0;i--)ret[i]=v[i]+ret[i+1];}else{for(inti=0;i<int(v.size());i++)ret[i+1]=ret[i]+v[i];}returnret;};template<typenameT>vector<T>mkuni(constvector<T>&v){vector<T>ret(v);sort(ret.begin(),ret.end());ret.erase(unique(ret.begin(),ret.end()),ret.end());returnret;}template<typenameF>vector<int>mkord(intN,Ff){vector<int>ord(N);iota(begin(ord),end(ord),0);sort(begin(ord),end(ord),f);returnord;}template<typenameT>vector<int>mkinv(vector<T>&v){intmax_val=*max_element(begin(v),end(v));vector<int>inv(max_val+1,-1);for(inti=0;i<(int)v.size();i++)inv[v[i]]=i;returninv;}vector<int>mkiota(intn){vector<int>ret(n);iota(begin(ret),end(ret),0);returnret;}template<typenameT>Tmkrev(constT&v){Tw{v};reverse(begin(w),end(w));returnw;}template<typenameT>boolnxp(T&v){returnnext_permutation(begin(v),end(v));}// 返り値の型は入力の T に依存// i 要素目 : [0, a[i])template<typenameT>vector<vector<T>>product(constvector<T>&a){vector<vector<T>>ret;vector<T>v;autodfs=[&](autorc,inti)->void{if(i==(int)a.size()){ret.push_back(v);return;}for(intj=0;j<a[i];j++)v.push_back(j),rc(rc,i+1),v.pop_back();};dfs(dfs,0);returnret;}// F : function(void(T&)), mod を取る操作// T : 整数型のときはオーバーフローに注意するtemplate<typenameT>TPower(Ta,longlongn,constT&I,constfunction<void(T&)>&f){Tres=I;for(;n;f(a=a*a),n>>=1){if(n&1)f(res=res*a);}returnres;}// T : 整数型のときはオーバーフローに注意するtemplate<typenameT>TPower(Ta,longlongn,constT&I=T{1}){returnPower(a,n,I,function<void(T&)>{[](T&)->void{}});}template<typenameT>TRev(constT&v){Tres=v;reverse(begin(res),end(res));returnres;}template<typenameT>vector<T>Transpose(constvector<T>&v){usingU=typenameT::value_type;if(v.empty())return{};intH=v.size(),W=v[0].size();vectorres(W,T(H,U{}));for(inti=0;i<H;i++){for(intj=0;j<W;j++){res[j][i]=v[i][j];}}returnres;}template<typenameT>vector<T>Rotate(constvector<T>&v,intclockwise=true){usingU=typenameT::value_type;intH=v.size(),W=v[0].size();vectorres(W,T(H,U{}));for(inti=0;i<H;i++){for(intj=0;j<W;j++){if(clockwise){res[W-1-j][i]=v[i][j];}else{res[j][H-1-i]=v[i][j];}}}returnres;}}// namespace Nyaan#line 58 "template/template.hpp"
// bit operation#line 1 "template/bitop.hpp"
namespaceNyaan{__attribute__((target("popcnt")))inlineintpopcnt(constu64&a){return__builtin_popcountll(a);}inlineintlsb(constu64&a){returna?__builtin_ctzll(a):64;}inlineintctz(constu64&a){returna?__builtin_ctzll(a):64;}inlineintmsb(constu64&a){returna?63-__builtin_clzll(a):-1;}template<typenameT>inlineintgbit(constT&a,inti){return(a>>i)&1;}template<typenameT>inlinevoidsbit(T&a,inti,boolb){if(gbit(a,i)!=b)a^=T(1)<<i;}constexprlonglongPW(intn){return1LL<<n;}constexprlonglongMSK(intn){return(1LL<<n)-1;}}// namespace Nyaan#line 61 "template/template.hpp"
// inout#line 1 "template/inout.hpp"
namespaceNyaan{template<typenameT,typenameU>ostream&operator<<(ostream&os,constpair<T,U>&p){os<<p.first<<" "<<p.second;returnos;}template<typenameT,typenameU>istream&operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;returnis;}template<typenameT>ostream&operator<<(ostream&os,constvector<T>&v){ints=(int)v.size();for(inti=0;i<s;i++)os<<(i?" ":"")<<v[i];returnos;}template<typenameT>istream&operator>>(istream&is,vector<T>&v){for(auto&x:v)is>>x;returnis;}istream&operator>>(istream&is,__int128_t&x){stringS;is>>S;x=0;intflag=0;for(auto&c:S){if(c=='-'){flag=true;continue;}x*=10;x+=c-'0';}if(flag)x=-x;returnis;}istream&operator>>(istream&is,__uint128_t&x){stringS;is>>S;x=0;for(auto&c:S){x*=10;x+=c-'0';}returnis;}ostream&operator<<(ostream&os,__int128_tx){if(x==0)returnos<<0;if(x<0)os<<'-',x=-x;stringS;while(x)S.push_back('0'+x%10),x/=10;reverse(begin(S),end(S));returnos<<S;}ostream&operator<<(ostream&os,__uint128_tx){if(x==0)returnos<<0;stringS;while(x)S.push_back('0'+x%10),x/=10;reverse(begin(S),end(S));returnos<<S;}voidin(){}template<typenameT,class...U>voidin(T&t,U&...u){cin>>t;in(u...);}voidout(){cout<<"\n";}template<typenameT,class...U,charsep=' '>voidout(constT&t,constU&...u){cout<<t;if(sizeof...(u))cout<<sep;out(u...);}structIoSetupNya{IoSetupNya(){cin.tie(nullptr);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);cerr<<fixed<<setprecision(7);}}iosetupnya;}// namespace Nyaan#line 64 "template/template.hpp"
// debug#line 1 "template/debug.hpp"
namespaceDebugImpl{template<typenameU,typename=void>structis_specialize:false_type{};template<typenameU>structis_specialize<U,typenameconditional<false,typenameU::iterator,void>::type>:true_type{};template<typenameU>structis_specialize<U,typenameconditional<false,decltype(U::first),void>::type>:true_type{};template<typenameU>structis_specialize<U,enable_if_t<is_integral<U>::value,void>>:true_type{};voiddump(constchar&t){cerr<<t;}voiddump(conststring&t){cerr<<t;}voiddump(constbool&t){cerr<<(t?"true":"false");}voiddump(__int128_tt){if(t==0)cerr<<0;if(t<0)cerr<<'-',t=-t;stringS;while(t)S.push_back('0'+t%10),t/=10;reverse(begin(S),end(S));cerr<<S;}voiddump(__uint128_tt){if(t==0)cerr<<0;stringS;while(t)S.push_back('0'+t%10),t/=10;reverse(begin(S),end(S));cerr<<S;}template<typenameU,enable_if_t<!is_specialize<U>::value,nullptr_t>=nullptr>voiddump(constU&t){cerr<<t;}template<typenameT>voiddump(constT&t,enable_if_t<is_integral<T>::value>*=nullptr){stringres;if(t==Nyaan::inf)res="inf";ifconstexpr(is_signed<T>::value){if(t==-Nyaan::inf)res="-inf";}ifconstexpr(sizeof(T)==8){if(t==Nyaan::infLL)res="inf";ifconstexpr(is_signed<T>::value){if(t==-Nyaan::infLL)res="-inf";}}if(res.empty())res=to_string(t);cerr<<res;}template<typenameT,typenameU>voiddump(constpair<T,U>&);template<typenameT>voiddump(constpair<T*,int>&);template<typenameT>voiddump(constT&t,enable_if_t<!is_void<typenameT::iterator>::value>*=nullptr){cerr<<"[ ";for(autoit=t.begin();it!=t.end();){dump(*it);cerr<<(++it==t.end()?"":", ");}cerr<<" ]";}template<typenameT,typenameU>voiddump(constpair<T,U>&t){cerr<<"( ";dump(t.first);cerr<<", ";dump(t.second);cerr<<" )";}template<typenameT>voiddump(constpair<T*,int>&t){cerr<<"[ ";for(inti=0;i<t.second;i++){dump(t.first[i]);cerr<<(i==t.second-1?"":", ");}cerr<<" ]";}voidtrace(){cerr<<endl;}template<typenameHead,typename...Tail>voidtrace(Head&&head,Tail&&...tail){cerr<<" ";dump(head);if(sizeof...(tail)!=0)cerr<<",";trace(std::forward<Tail>(tail)...);}}// namespace DebugImpl#ifdef NyaanDebug
#define trc(...) \
do { \
cerr << "## " << #__VA_ARGS__ << " = "; \
DebugImpl::trace(__VA_ARGS__); \
} while (0)
#else
#define trc(...) (void(0))
#endif
#ifdef NyaanLocal
#define trc2(...) \
do { \
cerr << "## " << #__VA_ARGS__ << " = "; \
DebugImpl::trace(__VA_ARGS__); \
} while (0)
#else
#define trc2(...) (void(0))
#endif
#line 67 "template/template.hpp"
// macro#line 1 "template/macro.hpp"
#define each(x, v) for (auto&& x : v)
#define each2(x, y, v) for (auto&& [x, y] : v)
#define all(v) (v).begin(), (v).end()
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
#define reg(i, a, b) for (long long i = (a); i < (b); i++)
#define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--)
#define fi first
#define se second
#define ini(...) \
int __VA_ARGS__; \
in(__VA_ARGS__)
#define inl(...) \
long long __VA_ARGS__; \
in(__VA_ARGS__)
#define ins(...) \
string __VA_ARGS__; \
in(__VA_ARGS__)
#define in2(s, t) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i]); \
}
#define in3(s, t, u) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i]); \
}
#define in4(s, t, u, v) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i], v[i]); \
}
#define die(...) \
do { \
Nyaan::out(__VA_ARGS__); \
return; \
} while (0)
#line 70 "template/template.hpp"
namespaceNyaan{voidsolve();}intmain(){Nyaan::solve();}#line 4 "verify/verify-yosupo-fps/yosupo-polynomial-interpolation-fast.test.cpp"
//#line 2 "fps/fast-interpolate.hpp"
#line 4 "fps/fast-interpolate.hpp"
usingnamespacestd;#line 2 "fps/formal-power-series.hpp"
template<typenamemint>structFormalPowerSeries:vector<mint>{usingvector<mint>::vector;usingFPS=FormalPowerSeries;FPS&operator+=(constFPS&r){if(r.size()>this->size())this->resize(r.size());for(inti=0;i<(int)r.size();i++)(*this)[i]+=r[i];return*this;}FPS&operator+=(constmint&r){if(this->empty())this->resize(1);(*this)[0]+=r;return*this;}FPS&operator-=(constFPS&r){if(r.size()>this->size())this->resize(r.size());for(inti=0;i<(int)r.size();i++)(*this)[i]-=r[i];return*this;}FPS&operator-=(constmint&r){if(this->empty())this->resize(1);(*this)[0]-=r;return*this;}FPS&operator*=(constmint&v){for(intk=0;k<(int)this->size();k++)(*this)[k]*=v;return*this;}FPS&operator/=(constFPS&r){if(this->size()<r.size()){this->clear();return*this;}intn=this->size()-r.size()+1;if((int)r.size()<=64){FPSf(*this),g(r);g.shrink();mintcoeff=g.back().inverse();for(auto&x:g)x*=coeff;intdeg=(int)f.size()-(int)g.size()+1;intgs=g.size();FPSquo(deg);for(inti=deg-1;i>=0;i--){quo[i]=f[i+gs-1];for(intj=0;j<gs;j++)f[i+j]-=quo[i]*g[j];}*this=quo*coeff;this->resize(n,mint(0));return*this;}return*this=((*this).rev().pre(n)*r.rev().inv(n)).pre(n).rev();}FPS&operator%=(constFPS&r){*this-=*this/r*r;shrink();return*this;}FPSoperator+(constFPS&r)const{returnFPS(*this)+=r;}FPSoperator+(constmint&v)const{returnFPS(*this)+=v;}FPSoperator-(constFPS&r)const{returnFPS(*this)-=r;}FPSoperator-(constmint&v)const{returnFPS(*this)-=v;}FPSoperator*(constFPS&r)const{returnFPS(*this)*=r;}FPSoperator*(constmint&v)const{returnFPS(*this)*=v;}FPSoperator/(constFPS&r)const{returnFPS(*this)/=r;}FPSoperator%(constFPS&r)const{returnFPS(*this)%=r;}FPSoperator-()const{FPSret(this->size());for(inti=0;i<(int)this->size();i++)ret[i]=-(*this)[i];returnret;}voidshrink(){while(this->size()&&this->back()==mint(0))this->pop_back();}FPSrev()const{FPSret(*this);reverse(begin(ret),end(ret));returnret;}FPSdot(FPSr)const{FPSret(min(this->size(),r.size()));for(inti=0;i<(int)ret.size();i++)ret[i]=(*this)[i]*r[i];returnret;}// 前 sz 項を取ってくる。sz に足りない項は 0 埋めするFPSpre(intsz)const{FPSret(begin(*this),begin(*this)+min((int)this->size(),sz));if((int)ret.size()<sz)ret.resize(sz);returnret;}FPSoperator>>(intsz)const{if((int)this->size()<=sz)return{};FPSret(*this);ret.erase(ret.begin(),ret.begin()+sz);returnret;}FPSoperator<<(intsz)const{FPSret(*this);ret.insert(ret.begin(),sz,mint(0));returnret;}FPSdiff()const{constintn=(int)this->size();FPSret(max(0,n-1));mintone(1),coeff(1);for(inti=1;i<n;i++){ret[i-1]=(*this)[i]*coeff;coeff+=one;}returnret;}FPSintegral()const{constintn=(int)this->size();FPSret(n+1);ret[0]=mint(0);if(n>0)ret[1]=mint(1);automod=mint::get_mod();for(inti=2;i<=n;i++)ret[i]=(-ret[mod%i])*(mod/i);for(inti=0;i<n;i++)ret[i+1]*=(*this)[i];returnret;}minteval(mintx)const{mintr=0,w=1;for(auto&v:*this)r+=w*v,w*=x;returnr;}FPSlog(intdeg=-1)const{assert(!(*this).empty()&&(*this)[0]==mint(1));if(deg==-1)deg=(int)this->size();return(this->diff()*this->inv(deg)).pre(deg-1).integral();}FPSpow(int64_tk,intdeg=-1)const{constintn=(int)this->size();if(deg==-1)deg=n;if(k==0){FPSret(deg);if(deg)ret[0]=1;returnret;}for(inti=0;i<n;i++){if((*this)[i]!=mint(0)){mintrev=mint(1)/(*this)[i];FPSret=(((*this*rev)>>i).log(deg)*k).exp(deg);ret*=(*this)[i].pow(k);ret=(ret<<(i*k)).pre(deg);if((int)ret.size()<deg)ret.resize(deg,mint(0));returnret;}if(__int128_t(i+1)*k>=deg)returnFPS(deg,mint(0));}returnFPS(deg,mint(0));}staticvoid*ntt_ptr;staticvoidset_fft();FPS&operator*=(constFPS&r);voidntt();voidintt();voidntt_doubling();staticintntt_pr();FPSinv(intdeg=-1)const;FPSexp(intdeg=-1)const;};template<typenamemint>void*FormalPowerSeries<mint>::ntt_ptr=nullptr;/**
* @brief 多項式/形式的冪級数ライブラリ
* @docs docs/fps/formal-power-series.md
*/#line 7 "fps/fast-interpolate.hpp"
// https://github.com/hos-lyric/libra/blob/master/algebra/poly_998244353.cpp// の多項式補間を手元で動くように改造// xs が distinct じゃないと壊れるtemplate<typenamemint>structSubproductTree{usingfps=FormalPowerSeries<mint>;intlogN,n,nn;vector<mint>xs;vector<mint>buf;vector<mint*>gss;fpsall,roots;voidntt(mint*a,ints)const{staticfpsbuf2;buf2.resize(s);copy(a,a+s,buf2.data());buf2.ntt();copy(buf2.data(),buf2.data()+s,a);}voidintt(mint*a,ints)const{staticfpsbuf2;buf2.resize(s);copy(a,a+s,buf2.data());buf2.intt();copy(buf2.data(),buf2.data()+s,a);}SubproductTree(constvector<mint>&xs_){n=xs_.size();for(logN=0,nn=1;nn<n;++logN,nn<<=1){}roots.resize(logN+1);for(inti=0;i<=logN;i++){intmod=mint::get_mod();roots[i]=mint{fps::ntt_pr()}.pow((mod-1)>>i);}xs.assign(nn,0U);memcpy(xs.data(),xs_.data(),n*sizeof(mint));buf.assign((logN+1)*(nn<<1),0U);gss.assign(nn<<1,nullptr);for(inth=0;h<=logN;++h)for(intu=1<<h;u<1<<(h+1);++u){gss[u]=buf.data()+(h*(nn<<1)+((u-(1<<h))<<(logN-h+1)));}for(inti=0;i<nn;++i){gss[nn+i][0]=-xs[i]+1;gss[nn+i][1]=-xs[i]-1;}if(nn==1)gss[1][1]+=2;for(inth=logN;--h>=0;){constintm=1<<(logN-h);for(intu=1<<(h+1);--u>=1<<h;){for(inti=0;i<m;++i)gss[u][i]=gss[u<<1][i]*gss[u<<1|1][i];memcpy(gss[u]+m,gss[u],m*sizeof(mint));intt(gss[u]+m,m);if(h>0){gss[u][m]-=2;constminta=roots[logN-h+1];mintaa=1;for(inti=m;i<m<<1;++i){gss[u][i]*=aa;aa*=a;};ntt(gss[u]+m,m);}}}all.resize(nn+1);all[0]=1;for(inti=1;i<nn;++i)all[i]=gss[1][nn+nn-i];all[nn]=gss[1][nn]-1;}vector<mint>multiEval(constfps&fs)const{vector<mint>work0(nn),work1(nn),work2(nn);{constintm=max<int>(fs.size(),1);autoinvAll=all.inv(m);std::reverse(invAll.begin(),invAll.end());intmm;for(mm=1;mm<m-1+nn;mm<<=1){}invAll.resize(mm,0U);ntt(invAll.data(),invAll.size());vector<mint>ffs(mm,0U);memcpy(ffs.data(),fs.data(),fs.size()*sizeof(mint));ntt(ffs.data(),ffs.size());for(inti=0;i<mm;++i)ffs[i]*=invAll[i];intt(ffs.data(),ffs.size());memcpy(((logN&1)?work1:work0).data(),ffs.data()+m-1,nn*sizeof(mint));}for(inth=0;h<logN;++h){constintm=1<<(logN-h);for(intu=1<<h;u<1<<(h+1);++u){mint*hs=(((logN-h)&1)?work1:work0).data()+((u-(1<<h))<<(logN-h));mint*hs0=(((logN-h)&1)?work0:work1).data()+((u-(1<<h))<<(logN-h));mint*hs1=hs0+(m>>1);ntt(hs,m);for(inti=0;i<m;++i)work2[i]=gss[u<<1|1][i]*hs[i];intt(work2.data(),m);memcpy(hs0,work2.data()+(m>>1),(m>>1)*sizeof(mint));for(inti=0;i<m;++i)work2[i]=gss[u<<1][i]*hs[i];intt(work2.data(),m);memcpy(hs1,work2.data()+(m>>1),(m>>1)*sizeof(mint));}}work0.resize(n);returnwork0;}fpsinterpolate(constvector<mint>&ys)const{assert(static_cast<int>(ys.size())==n);fpsgs(n);for(inti=0;i<n;++i)gs[i]=all[n-(i+1)]*(i+1);constvector<mint>denoms=multiEval(gs);vector<mint>work(nn<<1,0U);for(inti=0;i<n;++i){assert(denoms[i]!=0);work[i<<1]=work[i<<1|1]=ys[i]/denoms[i];}for(inth=logN;--h>=0;){constintm=1<<(logN-h);for(intu=1<<(h+1);--u>=1<<h;){mint*hs=work.data()+((u-(1<<h))<<(logN-h+1));for(inti=0;i<m;++i)hs[i]=gss[u<<1|1][i]*hs[i]+gss[u<<1][i]*hs[m+i];if(h>0){memcpy(hs+m,hs,m*sizeof(mint));intt(hs+m,m);constminta=roots[logN-h+1];mintaa=1;for(inti=m;i<m<<1;++i){hs[i]*=aa;aa*=a;};ntt(hs+m,m);}}}intt(work.data(),nn);return{work.data()+nn-n,work.data()+nn};}};#line 2 "fps/ntt-friendly-fps.hpp"
#line 2 "ntt/ntt.hpp"
template<typenamemint>structNTT{staticconstexpruint32_tget_pr(){uint32_t_mod=mint::get_mod();usingu64=uint64_t;u64ds[32]={};intidx=0;u64m=_mod-1;for(u64i=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){intflg=1;for(inti=0;i<idx;++i){u64a=_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;};staticconstexpruint32_tmod=mint::get_mod();staticconstexpruint32_tpr=get_pr();staticconstexprintlevel=__builtin_ctzll(mod-1);mintdw[level],dy[level];voidsetwy(intk){mintw[level],y[level];w[k-1]=mint(pr).pow((mod-1)/(1<<k));y[k-1]=w[k-1].inverse();for(inti=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],dy[1]=y[1],dw[2]=w[2],dy[2]=y[2];for(inti=3;i<k;++i){dw[i]=dw[i-1]*y[i-2]*w[i];dy[i]=dy[i-1]*w[i-2]*y[i];}}NTT(){setwy(level);}voidfft4(vector<mint>&a,intk){if((int)a.size()<=1)return;if(k==1){minta1=a[1];a[1]=a[0]-a[1];a[0]=a[0]+a1;return;}if(k&1){intv=1<<(k-1);for(intj=0;j<v;++j){mintajv=a[j+v];a[j+v]=a[j]-ajv;a[j]+=ajv;}}intu=1<<(2+(k&1));intv=1<<(k-2-(k&1));mintone=mint(1);mintimag=dw[1];while(v){// jh = 0{intj0=0;intj1=v;intj2=j1+v;intj3=j2+v;for(;j0<v;++j0,++j1,++j2,++j3){mintt0=a[j0],t1=a[j1],t2=a[j2],t3=a[j3];mintt0p2=t0+t2,t1p3=t1+t3;mintt0m2=t0-t2,t1m3=(t1-t3)*imag;a[j0]=t0p2+t1p3,a[j1]=t0p2-t1p3;a[j2]=t0m2+t1m3,a[j3]=t0m2-t1m3;}}// jh >= 1mintww=one,xx=one*dw[2],wx=one;for(intjh=4;jh<u;){ww=xx*xx,wx=ww*xx;intj0=jh*v;intje=j0+v;intj2=je+v;for(;j0<je;++j0,++j2){mintt0=a[j0],t1=a[j0+v]*xx,t2=a[j2]*ww,t3=a[j2+v]*wx;mintt0p2=t0+t2,t1p3=t1+t3;mintt0m2=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;}}voidifft4(vector<mint>&a,intk){if((int)a.size()<=1)return;if(k==1){minta1=a[1];a[1]=a[0]-a[1];a[0]=a[0]+a1;return;}intu=1<<(k-2);intv=1;mintone=mint(1);mintimag=dy[1];while(u){// jh = 0{intj0=0;intj1=v;intj2=v+v;intj3=j2+v;for(;j0<v;++j0,++j1,++j2,++j3){mintt0=a[j0],t1=a[j1],t2=a[j2],t3=a[j3];mintt0p1=t0+t1,t2p3=t2+t3;mintt0m1=t0-t1,t2m3=(t2-t3)*imag;a[j0]=t0p1+t2p3,a[j2]=t0p1-t2p3;a[j1]=t0m1+t2m3,a[j3]=t0m1-t2m3;}}// jh >= 1mintww=one,xx=one*dy[2],yy=one;u<<=2;for(intjh=4;jh<u;){ww=xx*xx,yy=xx*imag;intj0=jh*v;intje=j0+v;intj2=je+v;for(;j0<je;++j0,++j2){mintt0=a[j0],t1=a[j0+v],t2=a[j2],t3=a[j2+v];mintt0p1=t0+t1,t2p3=t2+t3;mintt0m1=(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*=dy[__builtin_ctzll(jh+=4)];}u>>=4;v<<=2;}if(k&1){u=1<<(k-1);for(intj=0;j<u;++j){mintajv=a[j]-a[j+u];a[j]+=a[j+u];a[j+u]=ajv;}}}voidntt(vector<mint>&a){if((int)a.size()<=1)return;fft4(a,__builtin_ctz(a.size()));}voidintt(vector<mint>&a){if((int)a.size()<=1)return;ifft4(a,__builtin_ctz(a.size()));mintiv=mint(a.size()).inverse();for(auto&x:a)x*=iv;}vector<mint>multiply(constvector<mint>&a,constvector<mint>&b){intl=a.size()+b.size()-1;if(min<int>(a.size(),b.size())<=40){vector<mint>s(l);for(inti=0;i<(int)a.size();++i)for(intj=0;j<(int)b.size();++j)s[i+j]+=a[i]*b[j];returns;}intk=2,M=4;while(M<l)M<<=1,++k;setwy(k);vector<mint>s(M);for(inti=0;i<(int)a.size();++i)s[i]=a[i];fft4(s,k);if(a.size()==b.size()&&a==b){for(inti=0;i<M;++i)s[i]*=s[i];}else{vector<mint>t(M);for(inti=0;i<(int)b.size();++i)t[i]=b[i];fft4(t,k);for(inti=0;i<M;++i)s[i]*=t[i];}ifft4(s,k);s.resize(l);mintinvm=mint(M).inverse();for(inti=0;i<l;++i)s[i]*=invm;returns;}voidntt_doubling(vector<mint>&a){intM=(int)a.size();autob=a;intt(b);mintr=1,zeta=mint(pr).pow((mint::get_mod()-1)/(M<<1));for(inti=0;i<M;i++)b[i]*=r,r*=zeta;ntt(b);copy(begin(b),end(b),back_inserter(a));}};#line 5 "fps/ntt-friendly-fps.hpp"
template<typenamemint>voidFormalPowerSeries<mint>::set_fft(){if(!ntt_ptr)ntt_ptr=newNTT<mint>;}template<typenamemint>FormalPowerSeries<mint>&FormalPowerSeries<mint>::operator*=(constFormalPowerSeries<mint>&r){if(this->empty()||r.empty()){this->clear();return*this;}set_fft();autoret=static_cast<NTT<mint>*>(ntt_ptr)->multiply(*this,r);return*this=FormalPowerSeries<mint>(ret.begin(),ret.end());}template<typenamemint>voidFormalPowerSeries<mint>::ntt(){set_fft();static_cast<NTT<mint>*>(ntt_ptr)->ntt(*this);}template<typenamemint>voidFormalPowerSeries<mint>::intt(){set_fft();static_cast<NTT<mint>*>(ntt_ptr)->intt(*this);}template<typenamemint>voidFormalPowerSeries<mint>::ntt_doubling(){set_fft();static_cast<NTT<mint>*>(ntt_ptr)->ntt_doubling(*this);}template<typenamemint>intFormalPowerSeries<mint>::ntt_pr(){set_fft();returnstatic_cast<NTT<mint>*>(ntt_ptr)->pr;}template<typenamemint>FormalPowerSeries<mint>FormalPowerSeries<mint>::inv(intdeg)const{assert((*this)[0]!=mint(0));if(deg==-1)deg=(int)this->size();FormalPowerSeries<mint>res(deg);res[0]={mint(1)/(*this)[0]};for(intd=1;d<deg;d<<=1){FormalPowerSeries<mint>f(2*d),g(2*d);for(intj=0;j<min((int)this->size(),2*d);j++)f[j]=(*this)[j];for(intj=0;j<d;j++)g[j]=res[j];f.ntt();g.ntt();for(intj=0;j<2*d;j++)f[j]*=g[j];f.intt();for(intj=0;j<d;j++)f[j]=0;f.ntt();for(intj=0;j<2*d;j++)f[j]*=g[j];f.intt();for(intj=d;j<min(2*d,deg);j++)res[j]=-f[j];}returnres.pre(deg);}template<typenamemint>FormalPowerSeries<mint>FormalPowerSeries<mint>::exp(intdeg)const{usingfps=FormalPowerSeries<mint>;assert((*this).size()==0||(*this)[0]==mint(0));if(deg==-1)deg=this->size();fpsinv;inv.reserve(deg+1);inv.push_back(mint(0));inv.push_back(mint(1));autoinplace_integral=[&](fps&F)->void{constintn=(int)F.size();automod=mint::get_mod();while((int)inv.size()<=n){inti=inv.size();inv.push_back((-inv[mod%i])*(mod/i));}F.insert(begin(F),mint(0));for(inti=1;i<=n;i++)F[i]*=inv[i];};autoinplace_diff=[](fps&F)->void{if(F.empty())return;F.erase(begin(F));mintcoeff=1,one=1;for(inti=0;i<(int)F.size();i++){F[i]*=coeff;coeff+=one;}};fpsb{1,1<(int)this->size()?(*this)[1]:0},c{1},z1,z2{1,1};for(intm=2;m<deg;m*=2){autoy=b;y.resize(2*m);y.ntt();z1=z2;fpsz(m);for(inti=0;i<m;++i)z[i]=y[i]*z1[i];z.intt();fill(begin(z),begin(z)+m/2,mint(0));z.ntt();for(inti=0;i<m;++i)z[i]*=-z1[i];z.intt();c.insert(end(c),begin(z)+m/2,end(z));z2=c;z2.resize(2*m);z2.ntt();fpsx(begin(*this),begin(*this)+min<int>(this->size(),m));x.resize(m);inplace_diff(x);x.push_back(mint(0));x.ntt();for(inti=0;i<m;++i)x[i]*=y[i];x.intt();x-=b.diff();x.resize(2*m);for(inti=0;i<m-1;++i)x[m+i]=x[i],x[i]=mint(0);x.ntt();for(inti=0;i<2*m;++i)x[i]*=z2[i];x.intt();x.pop_back();inplace_integral(x);for(inti=m;i<min<int>(this->size(),2*m);++i)x[i]+=(*this)[i];fill(begin(x),begin(x)+m,mint(0));x.ntt();for(inti=0;i<2*m;++i)x[i]*=y[i];x.intt();b.insert(end(b),begin(x)+m,end(x));}returnfps{begin(b),begin(b)+deg};}/**
* @brief NTT mod用FPSライブラリ
* @docs docs/fps/ntt-friendly-fps.md
*/#line 2 "modint/montgomery-modint.hpp"
template<uint32_tmod>structLazyMontgomeryModInt{usingmint=LazyMontgomeryModInt;usingi32=int32_t;usingu32=uint32_t;usingu64=uint64_t;staticconstexpru32get_r(){u32ret=mod;for(i32i=0;i<4;++i)ret*=2-mod*ret;returnret;}staticconstexpru32r=get_r();staticconstexpru32n2=-u64(mod)%mod;static_assert(mod<(1<<30),"invalid, mod >= 2 ^ 30");static_assert((mod&1)==1,"invalid, mod % 2 == 0");static_assert(r*mod==1,"this code has bugs.");u32a;constexprLazyMontgomeryModInt():a(0){}constexprLazyMontgomeryModInt(constint64_t&b):a(reduce(u64(b%mod+mod)*n2)){};staticconstexpru32reduce(constu64&b){return(b+u64(u32(b)*u32(-r))*mod)>>32;}constexprmint&operator+=(constmint&b){if(i32(a+=b.a-2*mod)<0)a+=2*mod;return*this;}constexprmint&operator-=(constmint&b){if(i32(a-=b.a)<0)a+=2*mod;return*this;}constexprmint&operator*=(constmint&b){a=reduce(u64(a)*b.a);return*this;}constexprmint&operator/=(constmint&b){*this*=b.inverse();return*this;}constexprmintoperator+(constmint&b)const{returnmint(*this)+=b;}constexprmintoperator-(constmint&b)const{returnmint(*this)-=b;}constexprmintoperator*(constmint&b)const{returnmint(*this)*=b;}constexprmintoperator/(constmint&b)const{returnmint(*this)/=b;}constexprbooloperator==(constmint&b)const{return(a>=mod?a-mod:a)==(b.a>=mod?b.a-mod:b.a);}constexprbooloperator!=(constmint&b)const{return(a>=mod?a-mod:a)!=(b.a>=mod?b.a-mod:b.a);}constexprmintoperator-()const{returnmint()-mint(*this);}constexprmintoperator+()const{returnmint(*this);}constexprmintpow(u64n)const{mintret(1),mul(*this);while(n>0){if(n&1)ret*=mul;mul*=mul;n>>=1;}returnret;}constexprmintinverse()const{intx=get(),y=mod,u=1,v=0,t=0,tmp=0;while(y>0){t=x/y;x-=t*y,u-=t*v;tmp=x,x=y,y=tmp;tmp=u,u=v,v=tmp;}returnmint{u};}friendostream&operator<<(ostream&os,constmint&b){returnos<<b.get();}friendistream&operator>>(istream&is,mint&b){int64_tt;is>>t;b=LazyMontgomeryModInt<mod>(t);return(is);}constexpru32get()const{u32ret=reduce(a);returnret>=mod?ret-mod:ret;}staticconstexpru32get_mod(){returnmod;}};#line 8 "verify/verify-yosupo-fps/yosupo-polynomial-interpolation-fast.test.cpp"
// #include "fps/arbitrary-fps.hpp"//usingnamespaceNyaan;usingmint=LazyMontgomeryModInt<998244353>;// using mint = LazyMontgomeryModInt<1000000007>;usingvm=vector<mint>;usingvvm=vector<vm>;usingfps=FormalPowerSeries<mint>;usingnamespaceNyaan;voidq(){ini(N);vmx(N),y(N);in(x,y);SubproductTreest{x};out(st.interpolate(y));}voidNyaan::solve(){intt=1;// in(t);while(t--)q();}