← 返回题目列表

AtCoder · arc074_c

E. RGB 序列

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

有 N 方块排成一排。 方块已编号 1, 2, ..., N,从左到右。

Snuke 正在将每个方块涂成红色、绿色或蓝色。 按照他的审美观,如下 M 条件必须全部满足。 的 i-第条件是:

  • 正好有 x_i 方块之间的颜色不同 l_i, l_i + 1, ..., r_i.

可以用多少种方法来绘制正方形以满足所有条件? 求计数模数 10^9+7.

约束

  • 1 ≤ N ≤ 300
  • 1 ≤ M ≤ 300
  • 1 ≤ l_i ≤ r_i ≤ N
  • 1 ≤ x_i ≤ 3

输入

输入由标准输入按以下格式给出:

N M
l_1 r_1 x_1
l_2 r_2 x_2
:
l_M r_M x_M

输出

打印满足所有条件的绘制正方形的方法数,模数 10^9+7.


示例输入 1

3 1
1 3 3

示例输出 1

6

这六种方式是:

  • RGB
  • RBG
  • GRB
  • 英国
  • BRG
  • BGR

其中 R、G 和 B 分别对应于红色、绿色和蓝色方块。


示例输入 2

4 2
1 3 1
2 4 2

示例输出 2

6

这六种方式是:

  • RRRG
  • RRRB
  • GGGR
  • GGGB
  • BBBR
  • BBBG

示例输入 3

1 3
1 1 1
1 1 2
1 1 3

示例输出 3

0

有零种方法。


示例输入 4

8 10
2 6 2
5 5 1
3 5 2
4 7 3
4 4 1
2 3 1
7 7 1
1 5 2
1 7 3
3 4 2

示例输出 4

108