奶牛游戏 "Moo Hunt"

贝西正在玩流行的游戏 "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$ 次操作中，贝西将轻拍 $3$ 个不同的单元格 $(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}$，贝西将获得一分。换句话说，如果贝西按 $x_i, y_i, z_i$ 的顺序轻拍单元格并形成字符串 "MOO"，她将获得一分。

农夫约翰想帮助贝西获得新的高分。他希望你在所有可能的棋盘中找到贝西可能获得的最大分数，以及能让贝西达到这个最大可能分数的不同棋盘的数量。如果存在一个单元格，使得两个棋盘在该单元格对应的字符不同，则认为这两个棋盘是不同的。

输入格式（从终端/stdin 输入）

第一行包含 $N$ 和 $K$，分别表示单元格数量和贝西将执行的操作次数。

接下来的 $K$ 行每行包含 $x_i, y_i, z_i$，描述贝西的第 $i$ 次操作（$x_i, y_i, z_i$ 两两不同）。

输出格式（打印输出到终端/stdout）

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

样例输入 1

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

样例输出 1

4 2

棋盘 MOOOM 和 MOOMM 允许贝西获得最大分数 $4$。在这两个棋盘上，贝西将在第 $1,2,5,6$ 次操作中获得分数。可以证明这是贝西能获得的最大分数，并且这两个棋盘是唯一能让贝西获得 $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

样例输出 2

6 3

能让贝西获得最大可能分数 $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$ 没有额外约束