npath

#include <bits/stdc++.h>

using namespace std;
ifstream f("npath.in");
ofstream g("npath.out");
const int MOD = 3000017;
int n,k,a[5005],b[5005],*A,*B;
vector<int> V[5005],O[5005];
bitset<5005> OO,VV;
int main()
{
    A=a;B=b;
    f>>n>>k;
    for(int i=1;i<=k;i++)
    {
        int x,y,d;
        f>>x>>y>>d;
        if(d==1)
            O[x].push_back(y+1);
        else
            V[x+1].push_back(y);
    }
    for(auto it:O[0])
        OO[it]=1;
    A[0]=1;
    for(int i=1;i<=n;i++)
            A[i]=(1-OO[i])*A[i-1];
    for(int j=1;j<=n;j++)
    {
        OO.reset();
        VV.reset();
        for(auto it:O[j])OO[it]=1;
        for(auto it:V[j])VV[it]=1;
        B[0]=(1-VV[0])*A[0];
        for(int i=1;i<=n;i++)
            B[i]=((1-OO[i])*B[i-1]+(1-VV[i])*A[i])%MOD;
        swap(A,B);
    }
    g<<A[n];
    return 0;
}