P15255 [USACO26JAN2] Moo Hunt B

Bessie 正在玩流行的游戏 Moo Hunt。在这个游戏中，有 $N$（$3 \le N \le 20$）个格子排成一行，编号从 $1$ 到 $N$。每个格子上的字符是 $M$ 或 $O$，第 $i$ 个格子上的字符为 $s_i$。 Bessie 计划进行 $K$（$1 \le K \le 2 \cdot 10^5$）次移动。在她的第 $i$ 次移动中，Bessie 会点击 $3$ 个不同的格子 $(x_{i}, y_{i}, z_{i})$（$1 \le x_{i}, y_{i}, z_{i} \le N$）。如果 $s_{x_i}=M$ 且 $s_{y_i}=s_{z_i}=O$，Bessie 将获得一分。换句话说，如果她按照顺序点击格子 $x_{i}, y_{i}, z_{i}$ 形成的字符串是 $MOO$，她就会得分。 Farmer John 想要帮助 Bessie 获得一个新的高分。他希望你在所有可能的棋盘配置中，找出 Bessie 进行这 $K$ 次移动所能获得的最大可能得分，以及能使 Bessie 达到这个最大可能得分的不同棋盘的数量。两个棋盘被认为是不同的，当且仅当存在一个格子，其上的字符不同。

第一行包含 $N$ 和 $K$，表示格子的数量和 Bessie 将进行的移动次数。 接下来的 $K$ 行，每行包含 $x_i, y_i, z_i$，描述 Bessie 的第 $i$ 次移动（$x_i, y_i, z_i$ 两两不同）。

输出 Bessie 所能获得的最大可能得分，以及能使 Bessie 达到这个最大得分的不同棋盘的数量。

#### 样例 1 解释 棋盘 $MOOOM$ 和 $MOOMM$ 可以使 Bessie 获得最大得分 $4$。在这两个棋盘上，Bessie 将在第 $1, 2, 5, 6$ 次移动中得分。可以证明这是 Bessie 能够获得的最大得分，并且只有这两个棋盘能使 Bessie 获得 $4$ 分。 #### 样例 2 解释 能使 Bessie 获得最大可能得分 $6$ 的棋盘是 $OOMOOO$、$OOMMOO$ 和 $OOMOOM$。 ### 评分 - 输入 3-5：$N \le 8, K \le 10^4$ - 输入 6-12：每个测试对应一个 $N \in \{14,15,16,17,18,19,20\}$，且对 $K$ 没有额外限制。 翻译由 DeepSeek 完成