#line 1 "library/Template/template.hpp" #include using namespace std; #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(v) (v).begin(),(v).end() using ll=long long int; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; templateinline bool chmax(T& a,T b){if(ainline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} #line 2 "library/Utility/fastio.hpp" #include class FastIO{ static constexpr int L=1<<16; char rdbuf[L]; int rdLeft=0,rdRight=0; inline void reload(){ int len=rdRight-rdLeft; memmove(rdbuf,rdbuf+rdLeft,len); rdLeft=0,rdRight=len; rdRight+=fread(rdbuf+len,1,L-len,stdin); } inline bool skip(){ for(;;){ while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++; if(rdLeft==rdRight){ reload(); if(rdLeft==rdRight)return false; } else break; } return true; } template::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdLeft::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft='0' and rdbuf[rdLeft]<='9' and rdLeft=rdRight)reload(); x=rdbuf[rdLeft++]; return true; } inline bool _read(string& x){ if(!skip())return false; for(;;){ int pos=rdLeft; while(pos' ')pos++; x.append(rdbuf+rdLeft,pos-rdLeft); if(rdLeft==pos)break; rdLeft=pos; if(rdLeft==rdRight)reload(); else break; } return true; } templateinline bool _read(vector& v){ for(auto& x:v){ if(!_read(x))return false; } return true; } char wtbuf[L],tmp[50]; int wtRight=0; inline void flush(){ fwrite(wtbuf,1,wtRight,stdout); wtRight=0; } inline void _write(const char& x){ if(wtRight>L-32)flush(); wtbuf[wtRight++]=x; } inline void _write(const string& x){ for(auto& c:x)_write(c); } template::value,int> =0>inline void _write(T x){ if(wtRight>L-32)flush(); if(x==0){ _write('0'); return; } else if(x<0){ _write('-'); if (__builtin_expect(x == std::numeric_limits::min(), 0)) { switch (sizeof(x)) { case 2: _write("32768"); return; case 4: _write("2147483648"); return; case 8: _write("9223372036854775808"); return; } } x=-x; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } templateinline void _write(const vector& v){ rep(i,0,v.size()){ if(i)_write(' '); _write(v[i]); } } public: FastIO(){} ~FastIO(){flush();} inline void read(){} template inline void read(Head& head,Tail&... tail){ assert(_read(head)); read(tail...); } templateinline void write(){if(ln)_write('\n');} template inline void write(const Head& head,const Tail&... tail){ if(space)_write(' '); _write(head); write(tail...); } }; /** * @brief Fast IO */ #line 3 "sol.cpp" #line 2 "library/Math/modint.hpp" templatestruct fp { int v; static int get_mod(){return mod;} int inv() const{ int tmp,a=v,b=mod,x=1,y=0; while(b)tmp=a/b,a-=tmp*b,swap(a,b),x-=tmp*y,swap(x,y); if(x<0){x+=mod;} return x; } fp(ll x=0){init(x%mod+mod);} fp& init(int x){v=(x>=1;} return res;} fp& operator+=(const fp& x){return init(v+x.v);} fp& operator-=(const fp& x){return init(v+mod-x.v);} fp& operator*=(const fp& x){v=ll(v)*x.v%mod; return *this;} fp& operator/=(const fp& x){v=ll(v)*x.inv()%mod; return *this;} fp operator+(const fp& x)const{return fp(*this)+=x;} fp operator-(const fp& x)const{return fp(*this)-=x;} fp operator*(const fp& x)const{return fp(*this)*=x;} fp operator/(const fp& x)const{return fp(*this)/=x;} bool operator==(const fp& x)const{return v==x.v;} bool operator!=(const fp& x)const{return v!=x.v;} friend istream& operator>>(istream& is,fp& x){return is>>x.v;} friend ostream& operator<<(ostream& os,const fp& x){return os<struct factorial { vector Fact,Finv,Inv; factorial(int maxx){ Fact.resize(maxx); Finv.resize(maxx); Inv.resize(maxx); Fact[0]=Fact[1]=Finv[0]=Finv[1]=Inv[1]=1; rep(i,2,maxx){Fact[i]=Fact[i-1]*i;} Finv[maxx-1]=Fact[maxx-1].inv(); for(int i=maxx-1;i>=2;i--){Finv[i-1]=Finv[i]*i; Inv[i]=Finv[i]*Fact[i-1];} } T fact(int n,bool inv=0){if(n<0)return 0; return (inv?Finv[n]:Fact[n]);} T inv(int n){if(n<0)return 0; return Inv[n];} T nPr(int n,int r,bool inv=0){if(n<0||nstruct NTT{ vector rt,irt; NTT(int lg=21){ unsigned m=T::get_mod()-1; T prt=p; rt.resize(lg); irt.resize(lg); rep(k,0,lg){ rt[k]=-prt.pow(m>>(k+2)); irt[k]=rt[k].inv(); } } void ntt(vector& f,bool inv=0){ int n=f.size(); if(inv){ for(int m=1;m>=1;){ T w=1; for(int s=0,t=0;s mult(const vector& a,const vector& b,bool same=0){ if(a.empty() or b.empty())return vector(); int n=a.size()+b.size()-1,m=1<<__lg(n*2-1); vector res(m); rep(i,0,a.size()){res[i]=a[i];} ntt(res); if(same)rep(i,0,m)res[i]*=res[i]; else{ vector c(m); rep(i,0,b.size())c[i]=b[i]; ntt(c); rep(i,0,m)res[i]*=c[i]; } ntt(res,1); res.resize(n); return res; } }; /** * @brief Number Theoretic Transform */ #line 2 "library/FPS/fps.hpp" templatestruct Poly:vector{ Poly(int n=0){this->assign(n,T());} Poly(const vector& f){this->assign(ALL(f));} T eval(const T& x){ T res; for(int i=this->size()-1;i>=0;i--)res*=x,res+=this->at(i); return res; } Poly rev()const{Poly res=*this; reverse(ALL(res)); return res;} void shrink(){while(!this->empty() and this->back()==0)this->pop_back();} vector mult(const vector& a,const vector& b,bool same=0)const{ if(a.empty() or b.empty())return vector(); int n=a.size()+b.size()-1,m=1<<__lg(n*2-1); vector res(m); rep(i,0,a.size())res[i]=a[i]; NTT(res,0); if(same)rep(i,0,m)res[i]*=res[i]; else{ vector c(m); rep(i,0,b.size())c[i]=b[i]; NTT(c,0); rep(i,0,m)res[i]*=c[i]; } NTT(res,1); res.resize(n); return res; } Poly square()const{return Poly(mult(*this,*this,1));} Poly operator+(const Poly& g)const{return Poly(*this)+=g;} Poly operator+(const T& g)const{return Poly(*this)+=g;} Poly operator-(const Poly& g)const{return Poly(*this)-=g;} Poly operator-(const T& g)const{return Poly(*this)-=g;} Poly operator*(const Poly& g)const{return Poly(*this)*=g;} Poly operator*(const T& g)const{return Poly(*this)*=g;} Poly operator/(const Poly& g)const{return Poly(*this)/=g;} Poly operator%(const Poly& g)const{return Poly(*this)%=g;} Poly& operator+=(const Poly& g){ if(g.size()>this->size())this->resize(g.size()); rep(i,0,g.size()){(*this)[i]+=g[i];} return *this; } Poly& operator+=(const T& g){ if(this->empty())this->push_back(0); (*this)[0]+=g; return *this; } Poly& operator-=(const Poly& g){ if(g.size()>this->size())this->resize(g.size()); rep(i,0,g.size()){(*this)[i]-=g[i];} return *this; } Poly& operator-=(const T& g){ if(this->empty())this->push_back(0); (*this)[0]-=g; return *this; } Poly& operator*=(const Poly& g){ *this=mult(*this,g,0); return *this; } Poly& operator*=(const T& g){ rep(i,0,this->size())(*this)[i]*=g; return *this; } Poly& operator/=(const Poly& g){ if(g.size()>this->size()){ this->clear(); return *this; } Poly g2=g; reverse(ALL(*this)); reverse(ALL(g2)); int n=this->size()-g2.size()+1; this->resize(n); g2.resize(n); *this*=g2.inv(); this->resize(n); reverse(ALL(*this)); shrink(); return *this; } Poly& operator%=(const Poly& g){*this-=*this/g*g; shrink(); return *this;} Poly diff()const{ Poly res(this->size()-1); rep(i,0,res.size())res[i]=(*this)[i+1]*(i+1); return res; } Poly inte()const{ Poly res(this->size()+1); for(int i=res.size()-1;i;i--)res[i]=(*this)[i-1]/i; return res; } Poly log()const{ assert(this->front()==1); const int n=this->size(); Poly res=diff()*inv(); res=res.inte(); res.resize(n); return res; } Poly shift(const int& c)const{ const int n=this->size(); Poly res=*this,g(n); g[0]=1; rep(i,1,n)g[i]=g[i-1]*c/i; vector fact(n,1); rep(i,0,n){ if(i)fact[i]=fact[i-1]*i; res[i]*=fact[i]; } res=res.rev(); res*=g; res.resize(n); res=res.rev(); rep(i,0,n)res[i]/=fact[i]; return res; } Poly inv()const{ const int n=this->size(); Poly res(1); res.front()=T(1)/this->front(); for(int k=1;ksize(); if(n==1)return Poly({T(1)}); Poly b(2),c(1),z1,z2(2); b[0]=c[0]=z2[0]=z2[1]=1; b[1]=(*this)[1]; for(int k=2;k>1)z[i]=0; NTT(z,0); rep(i,0,k)z[i]*=-z1[i]; NTT(z,1); c.insert(c.end(),z.begin()+(k>>1),z.end()); z2=c; z2.resize(k*2); NTT(z2,0); Poly x=*this; x.resize(k); x=x.diff();x.resize(k); NTT(x,0); rep(i,0,k)x[i]*=y[i]; NTT(x,1); Poly bb=b.diff(); rep(i,0,k-1)x[i]-=bb[i]; x.resize(k*2); rep(i,0,k-1){x[k+i]=x[i]; x[i]=0;} NTT(x,0); rep(i,0,k*2)x[i]*=z2[i]; NTT(x,1); x.pop_back(); x=x.inte(); rep(i,k,min(n,k*2))x[i]+=(*this)[i]; rep(i,0,k)x[i]=0; NTT(x,0); rep(i,0,k*2)x[i]*=y[i]; NTT(x,1); b.insert(b.end(),x.begin()+k,x.end()); } b.resize(n); return b; } Poly pow(ll t){ int n=this->size(),k=0; while(k=n)return res; n-=t*k; Poly g(n); T c=(*this)[k],ic=T(1)/c; rep(i,0,n)g[i]=(*this)[i+k]*ic; g=g.log(); for(auto& x:g)x*=t; g=g.exp(); c=c.pow(t); rep(i,0,n)res[i+t*k]=g[i]*c; return res; } void NTT(vector& a,bool inv)const; }; /** * @brief Formal Power Series (NTT-friendly mod) */ #line 7 "sol.cpp" using Fp=fp<998244353>; NTT ntt; template<>void Poly::NTT(vector& v,bool inv)const{return ntt.ntt(v,inv);} #line 2 "library/Math/bbla.hpp" #line 2 "library/FPS/berlekampmassey.hpp" templatevector BerlekampMassey(vector& a){ int n=a.size(); T d=1; vector b(1),c(1); b[0]=c[0]=1; rep(j,1,n+1){ int l=c.size(),m=b.size(); T x=0; rep(i,0,l)x+=c[i]*a[j-l+i]; b.push_back(0); m++; if(x==0)continue; T coeff=-x/d; if(l>8)); } unsigned get(unsigned L){ return get()%(L+1); } templateT get(T L,T R){ return get(R-L)+L; } double uniform(){ return double(get())/UINT_MAX; } string str(int n){ string ret; rep(i,0,n)ret+=get('a','z'); return ret; } templatevoid shuffle(Iter first,Iter last){ if(first==last)return; int len=1; for(auto it=first+1;it!=last;it++){ len++; int j=get(0,len-1); if(j!=len-1)iter_swap(it,first+j); } } templatevector select(int n,T L,T R){ set ret; while(ret.size()Poly RandPoly(int n){ Poly ret(n); for(auto& x:ret)x=genBBLA.get(1,T::get_mod()-1); return ret; } templatestruct SparseMatrix{ vector base; SparseMatrix(int n):base(n,1){} int size()const{return base.size();} friend Poly operator*(const SparseMatrix& A,const Poly& b){ Poly ret=A.apply(b); rep(i,0,ret.size())ret[i]*=A.base[i]; return ret; } void mul(int i,T x){base[i]*=x;} Poly apply(const Poly& b)const; }; templatePoly MinPolyforVector(const vector>& b){ int n=b.size(),m=b[0].size(); Poly base=RandPoly(m),a(n); rep(i,0,n)rep(j,0,m)a[i]+=base[j]*b[i][j]; return Poly(BerlekampMassey(a)).rev(); } templatePoly MinPolyforMatrix(const SparseMatrix& A){ int n=A.size(); Poly base=RandPoly(n); vector> b(n*2+1); rep(i,0,n*2+1)b[i]=base,base=A*base; return MinPolyforVector(b); } templatePoly FastPow(const SparseMatrix& A,Poly b,ll t){ int n=A.size(); auto mp=MinPolyforMatrix(A); Poly cs({T(1)}),base({T(0),T(1)}); while(t){ if(t&1)cs=(cs*base)%mp; base=base.square(); base%=mp; t>>=1; } Poly ret(n); for(auto& c:cs)ret+=b*c,b=A*b; return ret; } templateT FastDet(const SparseMatrix& A){ int n=A.size(); for(;;){ Poly d=RandPoly(n); SparseMatrix AD=A; rep(i,0,n)AD.mul(i,d[i]); auto mp=MinPolyforMatrix(AD); if(mp.back()==0)return 0; if(int(mp.size())!=n+1)continue; T ret=mp.back(),base=1; if(n&1)ret=-ret; for(auto& v:d)base*=v; return ret/base; } } /** * @brief Black Box Linear Algebra */ #line 12 "sol.cpp" vector as,bs,cs; template<>Poly SparseMatrix::apply(const Poly& b)const{ Poly ret(b.size()); rep(i,0,as.size()){ ret[as[i]]+=b[bs[i]]*cs[i]; } return ret; } FastIO io; int main(){ int k,m; ll n; io.read(k,m,n); rep(_,0,m){ int p,q,r; io.read(p,q,r); p--; q--; r--; as.push_back(p*k+q); bs.push_back(q*k+r); cs.push_back(1); } SparseMatrix A(k*k); Poly b(k*k); rep(i,0,k)b[i*k]=1; auto c=FastPow(A,b,n-2); Fp ret; rep(i,0,k)ret+=c[i]; io.write(ret.v); return 0; }