output_description: Print the number of ways to paint the squares to satisfy all the conditions,
  modulo 10^9+7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      l_1 r_1 x_1
      l_2 r_2 x_2
      :
      l_M r_M x_M
attempt: MOD = 10**9 + 7
  N, M = map(int, input().split())
  S = [[N + 1] * (N + 1) for i in [0, 1, 2]]
  T = [[0] * (N + 1) for i in [0, 1, 2]]
  
  C = [0] * (N + 1)
  for i in range(M):
      l, r, x = map(int, input().split())
      if r - l < x - 1:
          print(0)
          exit(0)
      S[x - 1][r] = min(S[x - 1][r], l)
      T[x - 1][r] = max(T[x - 1][r], l)
      C[r] = 1
  
  S0, S1, S2 = S
  T0, T1, T2 = T
  
  ok = 1
  for i in range(N + 1):
      if not T2[i] < S1[i] or not T1[i] < S0[i]:
          ok = 0
          break
  
  if not ok:
      print(0)
      exit(0)
  
  RM = [N + 1] * (N + 1)
  GM = [N + 1] * (N + 1)
  for i in range(N - 1, -1, -1):
      RM[i] = min(RM[i + 1], S1[i + 1])
      GM[i] = min(GM[i + 1], S0[i + 1])
  
  
  X = {(0, 0): 3}
  D = [0] * (N + 1)
  D[0] = 6
  B = [{} for i in range(N + 1)]
  B[0][0] = 3
  bb = 0
  for b in range(1, N):
      t2 = T2[b + 1]
      s1 = S1[b + 1]
      t1 = T1[b + 1]
      s0 = S0[b + 1]
  
      rm = RM[b]
      gm = GM[b]
      if t1 <= b < gm:
          F = B[b]
          for z in range(t2, min(rm, b)):
              v = D[z] % MOD
              if v:
                  F[z] = v
                  D[z] += v
                  D[b] += v
      if C[b + 1]:
          for g in range(bb, min(t1, b)):
              for r, v in B[g].items():
                  D[r] -= v
                  D[g] -= v
              B[g] = None
          bb = max(t1, bb)
          for g in range(bb, b):
              for r, v in B[g].items():
                  if not t2 <= r < s1:
                      D[r] -= v
                      D[g] -= v
              B[g] = {r: v for r, v in B[g].items() if t2 <= r < s1}
  ans = 0
  for b in range(bb, N + 1):
      if B[b]:
          ans += sum(B[b].values())
  print(ans % MOD)
  
problem_description: Statement
  
  There are N squares arranged in a row. The squares are numbered 1, 2, ..., N,
  from left to right.
  
  Snuke is painting each square in red, green or blue. According to his
  aesthetic sense, the following M conditions must all be satisfied. The i-th
  condition is:
  
    * There are exactly x_i different colors among squares l_i, l_i + 1, ..., r_i.
  
  In how many ways can the squares be painted to satisfy all the conditions?
  Find the count modulo 10^9+7.
samples: [{"input": "3 1\n    1 3 3", "output": "6\n    \n\nThe six ways are:\n\n  * RGB\n  * RBG\n  * GRB\n  * GBR\n  * BRG\n  * BGR\n\nwhere R, G and B correspond to red, green and blue squares, respectively.\n\n* * *"}, {"input": "4 2\n    1 3 1\n    2 4 2", "output": "6\n    \n\nThe six ways are:\n\n  * RRRG\n  * RRRB\n  * GGGR\n  * GGGB\n  * BBBR\n  * BBBG\n\n* * *"}, {"input": "1 3\n    1 1 1\n    1 1 2\n    1 1 3", "output": "0\n    \n\nThere are zero ways.\n\n* * *"}, {"input": "8 10\n    2 6 2\n    5 5 1\n    3 5 2\n    4 7 3\n    4 4 1\n    2 3 1\n    7 7 1\n    1 5 2\n    1 7 3\n    3 4 2", "output": "108"}]