문제

민준이는 인기 있는 게임인 "MOO 게임"을 하고 있다. 이 게임에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 칸이 일렬로 놓여 있다. 모든 칸에는 M 또는 O 중 하나의 문자가 적혀 있으며, $i$번째 칸에 적힌 문자를 $s_i$라고 한다.

민준이는 $K$번의 행동을 수행할 계획이다. $i$번째 행동에서 민준이는 서로 다른 세 칸 $(x_i, y_i, z_i)$을 선택한다. 만약 $s_{x_i} = \text{M}$이고 $s_{y_i} = s_{z_i} = \text{O}$라면 민준이는 $1$점을 얻는다. 다시 말해, 민준이가 선택한 세 칸의 문자를 순서대로 확인했을 때 문자열 MOO가 완성된다면 점수를 얻는 것이다.

민준이가 수행할 $K$번의 행동이 주어졌을 때, 가능한 모든 보드 구성($2^N$가지) 중에서 민준이가 얻을 수 있는 최대 점수와, 그 최대 점수를 얻을 수 있는 서로 다른 보드의 개수를 구한다. 두 보드에서 적어도 한 칸의 문자가 서로 다르다면 두 보드는 서로 다른 것으로 간주한다.

입력

첫째 줄에 칸의 개수 $N$과 민준이가 수행할 행동의 횟수 $K$가 공백으로 구분되어 주어진다. ($3 \le N \le 20$; $1 \le K \le 2 \cdot 10^5$)

이어서 $K$개의 줄에 걸쳐 각 줄마다 민준이의 $i$번째 행동을 나타내는 세 정수 $x_i, y_i, z_i$가 공백으로 구분되어 주어진다. ($1 \le x_i, y_i, z_i \le N$; $x_i, y_i, z_i$는 서로 다름)

출력

민준이가 얻을 수 있는 최대 점수와 해당 점수를 얻을 수 있는 보드의 개수를 공백으로 구분하여 출력한다.

예제 입력 1

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

예제 출력 1

4 2

예제 입력 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