分数: 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