K. 方块染色

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

个点排成一列,每个点都必须染成红绿蓝三种颜色中的恰好一种。现在有个要求,分别形如 。含义是从 的所有格子中(包括两端点)恰有 种不同的颜色。

求合法的染色方案数,答案对 取模。

输入格式

第一行两个整数 (),由空格隔开。

接下来行,每行3个整数 (),由空格隔开。

输出格式

输出一个整数表示方案数,对 取模。

样例

样例输入1

4 2
1 3 1
2 4 2

样例输出1

6

样例输入2

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

样例输出2

108