#include <bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define endl "\n" #define int long long const int MOD = 1e9 + 7; const int SZ = 20; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int getRand(int l, int r) { uniform_int_distribution<int> uid(l, r); return uid(rng); } int pow(int a, int b, int m) { int ans = 1; while(b > 0) { if(b % 2) { ans *= a; ans %= m; } a *= a; a %= m; b /= 2; } return ans; } int add(int a, int b) { int res = a + b; if(res >= MOD) return res - MOD; return res; } int mult(int a, int b) { long long res = a; res *= b; if(res >= MOD) return res % MOD; return res; } struct matrix { int arr[SZ][SZ]; void reset() { memset(arr, 0, sizeof(arr)); } void makeiden() { reset(); for(int i=0;i<SZ;i++) { arr[i][i] = 1; } } matrix operator + (const matrix &o) const { matrix res; for(int i=0;i<SZ;i++) { for(int j=0;j<SZ;j++) { res.arr[i][j] = add(arr[i][j], o.arr[i][j]); } } return res; } matrix operator * (const matrix &o) const { matrix res; for(int i=0;i<SZ;i++) { for(int j=0;j<SZ;j++) { res.arr[i][j] = 0; for(int k=0;k<SZ;k++) { res.arr[i][j] = add(res.arr[i][j] , mult(arr[i][k] , o.arr[k][j])); } } } return res; } }; matrix power(matrix a, int b) { matrix res; res.makeiden(); while(b) { if(b & 1) { res = res * a; } a = a * a; b >>= 1; } return res; } int work(int n, int g) { matrix mat; int temp = 0; for(int i = 0; i < 20; i++) { for(int j = 0; j < 20; j++) { mat.arr[i][j] = (__gcd(i + 1, j + 1) == g); temp += mat.arr[i][j]; } } matrix m = power(mat, n - 1); int sum = 0; for(int i = 0; i < 20; i++) for(int j = 0; j < 20; j++) sum += m.arr[i][j]; sum %= MOD; return sum; } int32_t main() { IOS; int n, m; cin >> n >> m; int others = n; int ans = 1; for(int i = 1; i <= m; i++) { int l, r, g; cin >> l >> r >> g; ans *= work(r - l + 1, g); ans %= MOD; others -= (r - l + 1); } ans *= pow(20LL, others, MOD); ans %= MOD; cout << ans; return 0; }