rt. WA on #6.

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    char c;int x,f{0};
    do x=(c=getchar())^48;
    while (!isdigit(c)&&c!='-');
    if (x==29) x=0,f=-1;
    while (isdigit(c=getchar()))
        x=(x<<3)+(x<<1)+(c^48);
    return (x^f)-f;
}
const int N(1e5),LG{16};
int f[LG+5][N+5];
int Find(int f[],int x){return x==f[x]?x:f[x]=Find(f,f[x]);}
void merge(int f[],int x,int y){Find(f,x)!=Find(f,y)&&(f[f[x]]=f[y]);}
int main() {
    int n{read()},m{read()};
    for (int j{0};j<=LG;++j)
        for (int i{1};i<=n;++i)
            f[j][i]=i;
    while (m--) {
        int a{read()},d{read()},b{read()};read();
        d+=-a+1;
        for (int i{0};d;++i,d>>=1)
            if (d&1) {
                merge(f[i],a,b);
                a+=1<<i;b+=1<<i;
            }
    }
    for (int i{1};i<=n;++i)
        for (int j{LG};j>=1;--j)
            if (i+(1<<j)-1<=n) {
                merge(f[j-1],i,f[j][i]);
                merge(f[j-1],i+(1<<j-1),f[j][i]+(1<<j-1));
            }
    int cnt{0};
    for (int i{1};i<=n;++i)
        cnt+=(f[0][i]==i);
    int ans{9};
    while (--cnt)
        ans=1LL*ans*10%(1000000007);
    cout<<ans<<endl;
    return 0;
}