Constrained GCD Array

Find the number of arrays of size N where each element of the array is in between 1 to 20, and that satisfy M requirements of the form:
Li Ri Gi, i.e., For every pair of consecutive elements in the range [Li , Ri] in the array, the GCD is Gi .
For example, a query of the form 3 6 5 means that gcd(A 3 , A 4 ) = gcd(A 4 , A 5 ) = gcd(A 5 , A 6 ) = 5 where A is the array and Ai denotes the i-th element of the array(1-based indexing).

It is guaranteed that no two query ranges([L i , R i ]) intersect.

Here GCD denotes greatest common divisor

Inputs:
First line contains two space-separated integers N and M
Next M lines contain three space-separated integers Li , Ri , Gi

Output:
The number of arrays satisfying the requirements.Since the answer can be too big,print it modulo 1000000007.

Constraints:
1 <= N <= 10 9
1 <= M <= 100
1 <= L i < R i <= N
1 <= G i <= 20

Sample Input
3 1
1 2 2

Sample Output
1260