该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

贝西正在玩流行的游戏"Moo Hunt"。游戏中有 $N$（$3 \leq N \leq 20$）个排成一行的格子，编号从 $1$ 到 $N$。每个格子包含字符 M 或 O，第 $i$ 个格子的字符为 $s_i$。

贝西计划进行 $K$（$1 \leq K \leq 2 \cdot 10^5$）次移动。在第 $i$ 次移动中，贝西会点击三个不同的格子 $(x_i, y_i, z_i)$（$1 \leq x_i, y_i, z_i \leq N$）。如果 $s_{x_i} = \text{M}$ 且 $s_{y_i} = s_{z_i} = \text{O}$，贝西就能得到 1 分。换句话说，如果贝西按顺序点击格子 $x_i, y_i, z_i$ 能形成字符串 "MOO"，她就能得分。

农夫约翰想帮助贝西获得新的高分。他希望你找出在所有可能的棋盘配置中，贝西能获得的最大可能分数，以及能让贝西达到这个最大分数的不同棋盘数量。如果两个棋盘在某个格子上的字符不同，则认为它们是不同的棋盘。

输入格式

第一行包含两个整数 $N$ 和 $K$，分别表示格子数量和贝西要进行的移动次数。

接下来的 $K$ 行，每行包含三个整数 $x_i, y_i, z_i$，描述贝西的第 $i$ 次移动（$x_i, y_i, z_i$ 两两不同）。

输出格式

输出贝西能获得的最大可能分数，然后输出能让贝西达到这个最大分数的不同棋盘数量。

5 6
1 2 3
1 2 3
1 3 5
2 3 4
5 3 2
5 2 3

4 2

6 12
2 4 3
2 3 4
3 5 2
3 5 1
3 1 5
3 1 2
6 1 5
1 6 4
2 3 6
3 6 2
4 1 6
3 4 2

6 2

样例解释一

棋盘配置 MOOOM 和 MOOMM 能让贝西获得最大分数 4。在这两种配置下，贝西能在第 1、2、5、6 次移动中得分。可以证明这是贝西能获得的最大分数，且只有这两个棋盘能让贝西获得 4 分。

样例解释二

能让贝西获得最大分数 6 的棋盘配置是：OOMOOO、OOMMOO 和 OOMOOM。

数据规模与约定

• 输入 3-5：$N \leq 8$，$K \leq 10^4$
• 输入 6-12：每个测试对应 $N \in \{14,15,16,17,18,19,20\}$ 中的一个值，对 $K$ 没有额外限制