//Twenty

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

using namespace std;

typedef long long LL;

const int maxn=1e5+;

const int mod=1e9+;

int f[maxn][],n,m;

void read(int &ret) {

    int f=; ret=; char ch=getchar();

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) ret=ret*+ch-''; ret*=f;

}

int find(int x,int l) {

    return x==f[x][l]?x:f[x][l]=find(f[x][l],l);

}

void link(int u,int v,int l) {

    if(find(u,l)==find(v,l)) return;

    f[f[u][l]][l]=f[v][l];

}

void init() {

    read(n); read(m);

    for(int i=;i<=n;i++)

        for(int j=;j<;j++)

            f[i][j]=i;

    for(int i=;i<=m;i++) {

        int a,b,c,d;

        read(a); read(b);

        read(c); read(d);

        for(int j=;j>=;j--) {

            if(a+(<<j)-<=b) {

                link(a,c,j);

                a+=(<<j);

                c+=(<<j);

            }

        }

    }

    for(int j=;j>=;j--) {

        for(int i=;(i+(<<j)-)<=n;i++) {

            link(i,find(i,j),j-);

            link(i+(<<j-),f[i][j]+(<<j-),j-);

        }

    }

    int cnt=;

    LL ans=;

    for(int i=;i<=n;i++)

        if(find(i,)==i) cnt++;

    for(int i=;i<cnt;i++) {

        (ans*=)%=mod;

    }

    printf("%lld\n",ans);

}

int main()

{

    init();

    return ;

}