{"problem":{"name":"RGB Sequence","description":{"content":"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 f","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc074_c"},"statements":[{"statement_type":"Markdown","content":"There are $N$ squares arranged in a row. The squares are numbered $1$, $2$, $...$, $N$, from left to right.\nSnuke 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:\n\n*   There are exactly $x_i$ different colors among squares $l_i$, $l_i + 1$, $...$, $r_i$.\n\nIn how many ways can the squares be painted to satisfy all the conditions? Find the count modulo $10^9+7$.\n\n## Constraints\n\n*   $1 ≤ N ≤ 300$\n*   $1 ≤ M ≤ 300$\n*   $1 ≤ l_i ≤ r_i ≤ N$\n*   $1 ≤ x_i ≤ 3$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$l_1$ $r_1$ $x_1$\n$l_2$ $r_2$ $x_2$\n$:$\n$l_M$ $r_M$ $x_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc074_c","tags":[],"sample_group":[["3 1\n1 3 3","6\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."],["4 2\n1 3 1\n2 4 2","6\n\nThe six ways are:\n\n*   RRRG\n*   RRRB\n*   GGGR\n*   GGGB\n*   BBBR\n*   BBBG"],["1 3\n1 1 1\n1 1 2\n1 1 3","0\n\nThere are zero ways."],["8 10\n2 6 2\n5 5 1\n3 5 2\n4 7 3\n4 4 1\n2 3 1\n7 7 1\n1 5 2\n1 7 3\n3 4 2","108"]],"created_at":"2026-03-03 11:01:13"}}