/* vectorの配列を吐き出す関数はvfillと同じ要領で簡潔に書けそう だけど面倒 vfillの範囲指定をできるようにしたい */ //#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags //#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX //#pragma GCC target("avx") //Enable AVX #pragma GCC optimize("Ofast") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll=int_fast64_t; using u64=uint_fast64_t; using pii=pair; using pil=pair; using pli=pair; using pll=pair; using psi=pair; using pis=pair; using psl=pair; using pls=pair; using pss=pair; //辺 fromあり template struct Edge { int from, to; T cost; Edge()=default; Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {} inline bool operator<(const Edge p)const noexcept{ return cost(const Edge p)const noexcept{ return cost>p.cost; } }; //辺 fromがない template struct edge { int to; T cost; edge()=default; edge(int _to, T _cost) : to(_to), cost(_cost) {} }; template using edges=vector>; template using WeightGraph=vector>; using Graph=vector>; templateinline constexpr bool chmin(T&a,const U b){if(a<=b)return false;a=b;return true;} templateinline constexpr bool chmax(T&a,const U b){if(a>=b)return false;a=b;return true;} #define bit(n,k) ( ( (n)>>(k) )&1 ) inline void bin101(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout< inline void vin1(vector &v){ for(size_t i=1;i>v[i]; } //0-indexed vector cin template inline void vin0(vector &v){ for(size_t i=0;i>v[i]; } //1-indexed vector cin template inline void vin1(vector> &v){ for(size_t i=1;i>v[i][j]; } } //0-indexed vector cin template inline void vin0(vector> &v){ for(size_t i=0;i>v[i][j]; } } bool DEBUG_MODE=false; #define debug(a) if(DEBUG_MODE){cout<<#a;PRINT(a);cout<void PRINT(const T x){cout<<":"< void PRINT(const vector &v,int a=-1){ if(!DEBUG_MODE) return; cout<<":1d\n"; for(size_t i=0;i void PRINT(const vector> &v,int a=-1,int b=-1){ if(!DEBUG_MODE) return; cout<<":2d\n"; for(size_t i=0;i void PRINT(const vector>> &v,int a=-1,int b=-1,int c=-1){ if(!DEBUG_MODE) return; cout<<":3d\n"; for(size_t i=0;i void PRINT(const vector>>> &v,int a=-1,int b=-1,int c=-1,int d=-1){ if(!DEBUG_MODE) return; cout<<":4d\n"; for(size_t i=0;i void PRINT(const vector>>>> &v,int a=-1,int b=-1,int c=-1,int d=-1,int e=-1){ if(!DEBUG_MODE) return; cout<<":5d\n"; for(size_t i=0;i void PRINT(const set &S){ if(!DEBUG_MODE) return; int now=0; for(auto x:S){ cout< void PRINT(const map &M){ if(!DEBUG_MODE) return; cout<<":map\n"; size_t now=0; for(auto &x:M){ cout< void GPRINT(const vector &v,int a=-1){ if(!DEBUG_MODE) return; cout<<":1d\n"; for(size_t i=0;i void GPRINT(const vector> &v,int a=-1,int b=-1){ if(!DEBUG_MODE) return; cout<<":2d\n"; for(size_t i=0;i inline ostream &operator<<(ostream &os,const pair &p) { os< inline istream &operator>>(istream &is,pair &p) { is>>p.first>>p.second; return is; } //ソート template inline void vsort(vector &v){ sort(v.begin(),v.end()); } //逆順ソート template inline void rvsort(vector &v){ sort(v.rbegin(),v.rend()); } //要素数n 初期値x template inline vector vmake(size_t n,T x){ return vector(n,x); } //a,b,c,x data[a][b][c] 初期値x template auto vmake(size_t n,Args... args){ auto v=vmake(args...); return vector(n,move(v)); } template inline void vfill(T &t,const X... x){ t=T(x...); } template void vfill(vector &t,const X... x){ for(auto &s:t) vfill(s,x...); } //最後に改行があるので注意 template void vout(const vector &v,string s=" ",size_t f=0,int t=-1){ for(size_t i=f;i void vout(const vector> &v,string s=" ",int fh=0,int th=-1,int fw=0,int tw=-1){ for(size_t i=fh;i=0)?(x%MOD):(x%MOD+MOD) ) {} inline constexpr ModInt operator+(const ModInt rhs)const noexcept{ return ModInt(*this)+=rhs; } inline constexpr ModInt operator-(const ModInt rhs)const noexcept{ return ModInt(*this)-=rhs; } inline constexpr ModInt operator*(const ModInt rhs)const noexcept{ return ModInt(*this)*=rhs; } inline constexpr ModInt operator/(const ModInt rhs)const noexcept{ return ModInt(*this)/=rhs; } inline constexpr ModInt operator+(const ll rhs) const noexcept{ return ModInt(*this)+=ModInt(rhs); } inline constexpr ModInt operator-(const ll rhs)const noexcept{ return ModInt(*this)-=ModInt(rhs); } inline constexpr ModInt operator*(const ll rhs)const noexcept{ return ModInt(*this)*=ModInt(rhs); } inline constexpr ModInt operator/(const ll rhs)const noexcept{ return ModInt(*this)/=ModInt(rhs); } inline constexpr ModInt &operator+=(const ModInt rhs)noexcept{ a+=rhs.a; if(a>=MOD) a-=MOD; return *this; } inline constexpr ModInt &operator-=(const ModInt rhs)noexcept{ if(rhs.a>a) a+=MOD; a-=rhs.a; return *this; } inline constexpr ModInt &operator*=(const ModInt rhs)noexcept{ a=(a*rhs.a)%MOD; return *this; } inline constexpr ModInt &operator/=(ModInt rhs)noexcept{ a=(a*rhs.inverse().a)%MOD; return *this; } inline constexpr ModInt &operator+=(const ll rhs)noexcept{ return *this+=ModInt(rhs); } inline constexpr ModInt &operator-=(const ll rhs)noexcept{ return *this-=ModInt(rhs); } inline constexpr ModInt &operator*=(const ll rhs)noexcept{ return *this*=ModInt(rhs); } inline constexpr ModInt &operator/=(const ll rhs)noexcept{ return *this/=ModInt(rhs); } inline constexpr ModInt operator=(const ll x)noexcept{ a=(x>=0)?(x%MOD):(x%MOD+MOD); return *this; } inline constexpr bool operator==(const ModInt p)const noexcept{ return a==p.a; } inline constexpr bool operator!=(const ModInt p)const noexcept{ return a!=p.a; } inline constexpr ModInt pow(ll N) const noexcept{ ModInt ans(1LL),p(a); while(N>0){ if(bit(N,0)){ ans*=p; } p*=p; N>>=1; } return ans; } inline constexpr ModInt inverse() const noexcept{ return pow(MOD-2); } }; inline constexpr ModInt operator+(const ll &a,const ModInt &b)noexcept{ return ModInt(a)+=b; } inline constexpr ModInt operator-(const ll &a,const ModInt &b)noexcept{ return ModInt(a)-=b; } inline constexpr ModInt operator*(const ll &a,const ModInt &b)noexcept{ return ModInt(a)*=b; } inline constexpr ModInt operator/(const ll &a,const ModInt &b)noexcept{ return ModInt(a)/=b; } //cout inline ostream &operator<<(ostream &os,const ModInt &p) { return os<>(istream &is,ModInt &p) { ll t; is>>t; p=t; return is; } struct Binominal{ vector fac,finv,inv; //fac[n]:n! finv:(n!)の逆元 int sz; Binominal(int n=10) :sz(1){ if(n<=0) n=10; init(n); } inline void init(int n){ fac.resize(n+1,1); finv.resize(n+1,1); inv.resize(n+1,1); for(int i=sz+1;i<=n;i++){ fac[i]=fac[i-1]*i; inv[i]=MOD-inv[MOD%i]*(MOD/i); finv[i]=finv[i-1]*inv[i]; } sz=n; } //nCk(n,k<=N) をO(1)で求める inline ModInt com(int n,int k){ if(nsz) init(n); return fac[n]*finv[k]*finv[n-k]; } //nCk(k<=N) をO(k) で求める inline ModInt rcom(ll n,int k){ if(n<0 || k<0 || nsz) init(k); ModInt ret(1); for(int i=0;i>N>>M>>K; auto dp=vmake(N,300,K+1,ModInt(0)); vector P(M),Q(M),C(M); for(int i=0;i>P[i]>>Q[i]>>C[i]; P[i]--; Q[i]--; } for(int i=0;i<300;i++){ dp[0][i][0]=1; } for(int i=0;i