ICPC 教练从不真正退休。当他们宣布“退休”时，他们实际上开始为一家秘密机构工作（我们不能透露更多细节），该机构在月球背面建造宏伟的建筑。目前有一个这样的项目正在进行中。

为了建造这座宏伟的建筑，他们可以使用两种不同类型的六边形建筑模块： 一个腔室 (chamber) 有三个开口，分别位于其三个互不相邻的边上。 一个连接件 (link) 有两个开口，分别位于两个相对的边上。

两个连接件（或一个连接件和一个腔室）可以沿着包含开口的边连接在一起；然后这些结构被焊接在一起，从而变得气密。

该计划是在月球表面建造一座包含 $N$ 个腔室的建筑。每个腔室都通过通道与另外三个腔室相连。每个通道由 $L$ 个连接件连接而成。通道的每一端（即开口所在的位置）都连接到一个腔室。例如，假设有 $N = 4$ 个编号为 1 到 4 的腔室，且 $L = 3$。下图展示了一种可能的结构（腔室以灰色阴影显示）：

保证任意两个腔室之间最多由一条通道连接，且没有通道连接腔室自身。此外，建筑内的人可以通过通道从任何一个腔室到达任何其他腔室。而且，该计划由前 CERC 教练制定，因此保证通道之间不会相互交叉（请记住该结构将建在月球表面）。这样的计划可以用一系列三元组来描述： $$(c_1^{(1)}, c_2^{(1)}, c_3^{(1)}), (c_1^{(2)}, c_2^{(2)}, c_3^{(2)}), \dots, (c_1^{(n)}, c_2^{(n)}, c_3^{(n)})$$

这意味着腔室 $i$ 连接到腔室 $c_1^{(i)}, c_2^{(i)}$ 和 $c_3^{(i)}$。如果一个人站在 $i$ 号腔室中并按顺时针方向旋转，该人将依次看到通往腔室 $c_1^{(i)}$ 的通道、通往腔室 $c_2^{(i)}$ 的通道，最后是通往腔室 $c_3^{(i)}$ 的通道。上述计划可以用以下序列描述： $$(2, 3, 4), (1, 4, 3), (1, 2, 4), (1, 3, 2)$$

由于月球背面是黑暗的（正如其名），每个建筑模块（无论是腔室还是连接件）的每一边都会安装一根霓虹灯管。当然，两个建筑模块焊接在一起的边只会有一根霓虹灯管。由于结构位于月球上，我们不应浪费太多能源，因此任何两条相邻的霓虹灯管不能同时点亮。教练们决定，为了提供充足的照明，他们将点亮最大数量的霓虹灯（在满足节能约束的前提下）。这样的照明方式被称为有效照明 (valid lighting)，甚至可以通过多种方式实现。下图展示了一种可能性：

教练们认为还有更多方法可以实现这一点。他们现在想知道有效照明的总数。由于他们太懒而不想编写代码，他们准备了一个竞赛题目，以便学生们能想出高效的解决方案。请编写一个程序，读取宏伟建筑的描述并确定有效照明的总数。由于结果可能是一个巨大的数字，请输出答案对 $10^6 + 3$ 取模的结果。

输入格式

第一行包含空格分隔的整数 $N$ 和 $L$，其中 $N$ 是腔室的数量，$L$ 是每个通道中连接件的数量。接下来有 $N$ 行；第 $i$ 行包含空格分隔的整数 $c_1^{(i)}, c_2^{(i)}$ 和 $c_3^{(i)}$。

数据范围

• $4 \le N \le 16$
• $1 \le L \le 100$
• $1 \le c_j^{(i)} \le N$，其中 $j = 1, 2, 3$ 且 $i = 1, 2, \dots, N$

输出格式

输出一个整数：有效照明的总数对 $10^6 + 3$ 取模的结果。

样例

输入 1

4 3
2 3 4
1 4 3
1 2 4
1 3 2

输出 1

4400