P15255 [USACO26JAN2] Moo Hunt B

Bessie is playing the popular game "Moo Hunt". In this game, there are $N$ ($3 \le N \le 20$) cells in a line, numbered from $1$ to $N$. All cells either have the character $M$ or $O$ with the $i$-th cell having character $s_i$. Bessie plans to perform $K$ ($1 \le K \le 2 \cdot 10^5$) mooves. On her $i$-th moove, Bessie will tap $3$ different cells ($x_{i},y_{i},z_{i}$) ($1 \le x_{i},y_{i},z_{i} \le N$). Bessie will earn a point if $s_{x_i}=M$ and $s_{y_i}=s_{z_i}=O$. In other words, Bessie will earn a point if she forms the string $MOO$ by tapping cells $x_{i},y_{i},z_{i}$ in that order. Farmer John wants to help Bessie get a new high score. He wants you to find the maximum possible score Bessie could get across all possible boards if she performs the $K$ mooves as well as the number of different boards that will allow Bessie to achieve this maximum possible score. Two boards are different if there exists a cell such that the corresponding characters at the cell are different.

The first line contains $N$ and $K$, the number of cells and the number of mooves Bessie will perform. Each of the next $K$ lines contains $x_i, y_i, z_i$ describing Bessie's $i$-th move ($x_i, y_i, z_i$ are pairwise distinct).

Output the maximum possible score Bessie could achieve, followed by the count of different boards that will allow Bessie to achieve this maximum score.

### Sample 1 Explanation The boards $MOOOM$ and $MOOMM$ allow Bessie to achieve a maximum score of $4$. In both boards, Bessie will earn points on mooves $1,2,5,6$. It can be shown that this is the maximum score Bessie can achieve, and those two boards are the only possible boards allowing Bessie to achieve a score of $4$. ### Sample 2 Explanation The boards that allow Bessie to achieve a maximum possible score of $6$ are $OOMOOO$, $OOMMOO$, and $OOMOOM$. SCORING: - Inputs 3-5: $N \le 8, K \le 10^4$ - Inputs 6-12: There will be one test for each $N \in \{14,15,16,17,18,19,20\}$ with no additional constraints on $K$.