나이트 배치

아래 그림과 같이 나이트는 특정 칸을 공격한다 (칸 $S$ 에 있는 나이트는 X 로 표시된 칸들을 공격한다).

$3$ 개의 행과 $n$ 개의 열로 이루어진 $3 \times n$ 크기의 체스판이 있고 ($1 \le n \le 100$), 나이트를 놓을 수 없는 칸들의 집합 $Z$ 가 주어진다. 행은 위에서 아래로 $1$ 부터 $3$ 까지, 열은 왼쪽에서 오른쪽으로 $1$ 부터 $n$ 까지 번호를 매긴다.

나이트는 집합 $Z$ 에 속하지 않는 칸에만 놓을 수 있고, 놓인 두 나이트는 서로를 공격해서는 안 된다. 각 열에서 $Z$ 에 속하는 칸은 최대 한 개다. 집합 $Z$ 는 수열 $k_1, k_2, \ldots, k_n$ 으로 주어지며 각 $k_i \in \{0, 1, 2, 3\}$ 이다. $k_i = 0$ 이면 $i$ 번째 열에는 막힌 칸이 없고, 그렇지 않으면 $k_i$ 는 그 열에서 유일하게 막힌 칸의 행 번호다.

이 규칙에 따라 놓을 수 있는 나이트의 최대 개수 $M$ 과, 정확히 $M$ 개의 나이트를 놓는 서로 다른 배치의 수 $L$ 을 구하여라.

첫째 줄에 열의 개수를 나타내는 정수 $n$ 이 주어진다 ($1 \le n \le 100$). 다음 $n$ 개의 줄에는 각각 $\{0, 1, 2, 3\}$ 중 하나의 정수가 주어지며, 이는 $Z$ 를 나타내는 수열의 항 $k_1, k_2, \ldots, k_n$ 이다.

나이트의 최대 개수 $M$ 과 그 최대를 이루는 배치의 수 $L$ 을 한 칸의 공백으로 구분하여 출력한다.