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: from itertools import permutations
  n,m = map(int,input().split())
  lrx = [list(map(int,input().split())) for i in range(m)]
  lrx.sort(key = lambda x:x[1])
  mod = 10**9+7
  dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
  dp[0][0][0] = 1
  for l,r,t in lrx:
    if t != 1:
      for g in range(l):
        for b in range(max(1,g)):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
    if t != 2:
      for g in range(l,r):
        for b in range(l):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
    if t != 3:
      for g in range(l,r):
        for b in range(l,g):
          for x,y,z in permutations((r,g,b)):
            dp[x][y][z] = -1
  
  for r in range(n):
    for g in range(r):
      for b in range(max(1,g)):
        v = dp[r][g][b]
        if v == -1:
          continue
        if dp[mx+1][g][b] >= 0:
          dp[mx+1][g][b] += v
          dp[mx+1][g][b] %= mod
        if dp[r][mx+1][b] >= 0:
          dp[r][mx+1][b] += v
          dp[r][mx+1][b] %= mod
        if dp[r][g][mx+1] >= 0:
          dp[r][g][mx+1] += v
          dp[r][g][mx+1] %= mod
  ans = 0
  for i in range(n):
    for j in range(max(1,i)):
      for x,y,z in permutations((n,i,j)):
        if dp[x][y][z] >= 0:
          ans += dp[x][y][z]
          ans %= mod
  print(ans*6%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"}]