#include using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } template struct ModInt{ long long x; ModInt():x(0){} ModInt(long long 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);} ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;} ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;} ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;} ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;} 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(long long n)const{ ModInt ret(1),mul(x); while(n>0){ if(n&1) ret*=mul; mul*=mul;n>>=1; } return ret; } friend ostream &operator<<(ostream &os,const ModInt &p){return os<>(istream &is,ModInt &a){long long t;is>>t;a=ModInt(t);return (is);} static int get_mod(){return Mod;} }; template struct Precalc{ vector fact,finv,inv; int Mod; Precalc(int MX):fact(MX),finv(MX),inv(MX),Mod(T::get_mod()){ fact[0]=T(1),fact[1]=T(1),finv[0]=T(1),finv[1]=T(1),inv[1]=T(1); for(int i=2;i> partition_function_table(int n,int k){ vector> ret(n+1,vector(k+1,0)); ret[0][0]=1; for(int i=0;i<=n;i++)for(int j=1;j<=k;j++)if(i or j){ ret[i][j]=ret[i][j-1]; if(i-j>=0) ret[i][j]+=ret[i-j][j]; } return ret; } // n = y.size - 1 // n次の多項式f, f(0), f(k)の値がわかっていればf(t)が求まる // 1^k + ... n^k はk+1次多項式,k=1ならn(n+1)/2 T LagrangePolynomial(vector y,long long t){ int n=(int)y.size()-1; if(t<=n) return y[t]; T ret=T(0); vector l(n+1,1),r(n+1,1); for(int i=0;i0;i--) r[i-1]=r[i]*(t-i); for(int i=0;i<=n;i++){ T add=y[i]*l[i]*r[i]*finv[i]*finv[n-i]; ret+=((n-i)%2?-add:add); } return ret; } /* sum combination(n+x, x), x=l to r https://www.wolframalpha.com/input/?i=sum+combination%28n%2Bx+%2Cx%29%2C+x%3Dl+to+r&lang=ja check n+x < [COM_PRECALC_MAX] */ T sum_of_comb(int n,int l,int r){ if(l>r)return T(0); T ret=T(r+1)*com(n+r+1,r+1)-T(l)*com(l+n,l); ret/=T(n+1); return ret; } /* - sum of comb 2 https://www.wolframalpha.com/input/?i=sum+combination%28i%2Bj%2Ci%29%2C+i%3D0+to+a-1%2C+j%3D0+to+b-1&lang=ja https://yukicoder.me/problems/no/1489 sum binom(i+j,i) i=0 to a-1, j=0 to b-1 = ( binom(a+b,a-1)*(b+1)/a ) - 1 */ }; using mint=ModInt; Precalc F(600000); signed main(){ int N,M;cin>>N>>M; mint res=F.com(N*2,N)*N*2; rep(i,M){ int t,u,v;cin>>t>>u>>v; mint mi=F.com(u+v,u); if(t==1) u++; else v++; res-=F.com(N-u+N-v,N-u)*mi; } cout<