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: import sys
  from collections import defaultdict
  
  sys.setrecursionlimit(10**6)
  int1 = lambda x: int(x) - 1
  p2D = lambda x: print(*x, sep="\n")
  
  
  def MI():
      return map(int, sys.stdin.readline().split())
  
  
  def LI():
      return list(map(int, sys.stdin.readline().split()))
  
  
  def LLI(rows_number):
      return [LI() for _ in range(rows_number)]
  
  
  # 一番後ろの色を(赤に)固定した上で、もらうDPに書き換え
  def main():
      md = 10**9 + 7
      n, m = MI()
      rtol = defaultdict(list)
      for _ in range(m):
          l, r, x = MI()
          rtol[r].append([l, x])
      dp = [[0] * (n + 1) for _ in range(n + 1)]
      dp[0][0] = 1
      for k in range(1, n + 1):
          for i in range(k - 1):
              dp[i][k - 1] = dp[k - 1][i] = sum(dp[i][: k - 1])
          for l, x in rtol[k]:
              if x == 1:
                  for i in range(l, k):
                      for j in range(k):
                          dp[i][j] = dp[j][i] = 0
              if x == 2:
                  for i in range(l, k):
                      for j in range(i + 1, k):
                          dp[i][j] = dp[j][i] = 0
                  for i in range(l):
                      for j in range(i + 1):
                          dp[i][j] = dp[j][i] = 0
              if x == 3:
                  for i in range(l):
                      for j in range(k):
                          dp[i][j] = dp[j][i] = 0
  
      # p2D(dp)
      print(sum(sum(dr) for dr in dp) * 3)
  
  
  main()
  
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"}]