from sys import stdin,stdout
def ain():
    return map(int,sin().split())
def sin():
    return stdin.readline().strip()
def gcd(x,y):
    while(y):
        x,y=y,x%y
    return x
 
def multiply(a, b):
    mul = [[0 for x in range(20)]
            for y in range(20)];
    for i in range(20):
        for j in range(20):
            for k in range(20):
                x=(a[i][k] * b[k][j])%mod
                mul[i][j]=(mul[i][j]+x)%mod
 
    for i in range(20):
        for j in range(20):
            a[i][j] = mul[i][j]
    return a
def power(F, n,b1):
    if(n==1):
        return
    power(F,n/2,b1)
    F = multiply(F, F)
    if (n % 2 != 0):
        F = multiply(F, b1)
    return F
def ans(b,z,b1):
    power(b,z,b1)
    s=0
    for i in range(20):
        for j in range(20):
            s=(s+b[i][j])%mod
    return s
mod=10**9+7
n,m=ain()
if(m==0):
    print pow(20,n,mod)
    exit()
b=[]
for i in range(m):
    b.append(ain())
b.sort()
x=b[0][0]-1
t=1
for i in range(m):
    l,r,g=b[i][0],b[i][1],b[i][2]
    z=r-l
    w=[[0 for r in range(20)] for r in range(20)]
    w1=[[0 for r in range(20)] for r in range(20)]
    for j in range(1,21):
        for k in range(1,21):
            if(gcd(j,k)==g):
                w[j-1][k-1]=1
                w1[j-1][k-1]=1
    t=(t*ans(w,z,w1))%mod
    if(i!=0):
        x+=b[i][0]-b[i-1][1]-1
x+=n-b[m-1][1]
t=(t*pow(20,x,mod))%mod
print t
 

ZnJvbSBzeXMgaW1wb3J0IHN0ZGluLHN0ZG91dApkZWYgYWluKCk6CiAgICByZXR1cm4gbWFwKGludCxzaW4oKS5zcGxpdCgpKQpkZWYgc2luKCk6CiAgICByZXR1cm4gc3RkaW4ucmVhZGxpbmUoKS5zdHJpcCgpCmRlZiBnY2QoeCx5KToKICAgIHdoaWxlKHkpOgogICAgICAgIHgseT15LHgleQogICAgcmV0dXJuIHgKCmRlZiBtdWx0aXBseShhLCBiKToKICAgIG11bCA9IFtbMCBmb3IgeCBpbiByYW5nZSgyMCldCiAgICAgICAgICAgIGZvciB5IGluIHJhbmdlKDIwKV07CiAgICBmb3IgaSBpbiByYW5nZSgyMCk6CiAgICAgICAgZm9yIGogaW4gcmFuZ2UoMjApOgogICAgICAgICAgICBmb3IgayBpbiByYW5nZSgyMCk6CiAgICAgICAgICAgICAgICB4PShhW2ldW2tdICogYltrXVtqXSklbW9kCiAgICAgICAgICAgICAgICBtdWxbaV1bal09KG11bFtpXVtqXSt4KSVtb2QKCiAgICBmb3IgaSBpbiByYW5nZSgyMCk6CiAgICAgICAgZm9yIGogaW4gcmFuZ2UoMjApOgogICAgICAgICAgICBhW2ldW2pdID0gbXVsW2ldW2pdCiAgICByZXR1cm4gYQpkZWYgcG93ZXIoRiwgbixiMSk6CiAgICBpZihuPT0xKToKICAgICAgICByZXR1cm4KICAgIHBvd2VyKEYsbi8yLGIxKQogICAgRiA9IG11bHRpcGx5KEYsIEYpCiAgICBpZiAobiAlIDIgIT0gMCk6CiAgICAgICAgRiA9IG11bHRpcGx5KEYsIGIxKQogICAgcmV0dXJuIEYKZGVmIGFucyhiLHosYjEpOgogICAgcG93ZXIoYix6LGIxKQogICAgcz0wCiAgICBmb3IgaSBpbiByYW5nZSgyMCk6CiAgICAgICAgZm9yIGogaW4gcmFuZ2UoMjApOgogICAgICAgICAgICBzPShzK2JbaV1bal0pJW1vZAogICAgcmV0dXJuIHMKbW9kPTEwKio5KzcKbixtPWFpbigpCmlmKG09PTApOgogICAgcHJpbnQgcG93KDIwLG4sbW9kKQogICAgZXhpdCgpCmI9W10KZm9yIGkgaW4gcmFuZ2UobSk6CiAgICBiLmFwcGVuZChhaW4oKSkKYi5zb3J0KCkKeD1iWzBdWzBdLTEKdD0xCmZvciBpIGluIHJhbmdlKG0pOgogICAgbCxyLGc9YltpXVswXSxiW2ldWzFdLGJbaV1bMl0KICAgIHo9ci1sCiAgICB3PVtbMCBmb3IgciBpbiByYW5nZSgyMCldIGZvciByIGluIHJhbmdlKDIwKV0KICAgIHcxPVtbMCBmb3IgciBpbiByYW5nZSgyMCldIGZvciByIGluIHJhbmdlKDIwKV0KICAgIGZvciBqIGluIHJhbmdlKDEsMjEpOgogICAgICAgIGZvciBrIGluIHJhbmdlKDEsMjEpOgogICAgICAgICAgICBpZihnY2QoaixrKT09Zyk6CiAgICAgICAgICAgICAgICB3W2otMV1bay0xXT0xCiAgICAgICAgICAgICAgICB3MVtqLTFdW2stMV09MQogICAgdD0odCphbnModyx6LHcxKSklbW9kCiAgICBpZihpIT0wKToKICAgICAgICB4Kz1iW2ldWzBdLWJbaS0xXVsxXS0xCngrPW4tYlttLTFdWzFdCnQ9KHQqcG93KDIwLHgsbW9kKSklbW9kCnByaW50IHQK

MyAxCjEgMiAy

3 1
1 2 2