Description

In the year 2xyz, humans have already immigrated to Mars. Due to industrial needs, people have started mining on Mars. The mining area is a regular hexagon with side length $N$. For planning convenience, the entire area is divided into $6 \times N \times N$ regular triangular cells (see Figure $1$).

There are three mines of types $A$, $B$, $C$, and three refineries of types $a$, $b$, $c$. Each triangular cell can be a mine, a refinery, a mountain, or flatland.

The management requires building a transportation system such that there is a road between each mine and its corresponding refinery (i.e., $A$ connects to $a$, $B$ to $b$, $C$ to $c$), and the three roads do not cross each other (that is, no triangular cell may be used by two or more roads transporting different ores). Two triangular cells are adjacent if and only if they share a common edge; roads may be built only between adjacent cells, and the cost to build such a road segment is $1$.

Note that roads cannot be built on mountains. Due to a Martian financial crisis, the management wants to know the minimum total cost to build such a transportation system. Moreover, they want to know how many minimum-cost solutions there are.

Input Format

The first line contains an integer $N$, the side length of the regular hexagonal mining area.

Then follow $6 \times N \times N$ integers, given in $2 \times N$ lines, each containing $3 \times N$ integers, describing the current state of each cell. $0$ denotes flatland, $1, 2, 3$ denote the corresponding mine or refinery, and $4$ denotes mountain. (Sample $1$ corresponds to Figure $2$.)

There may be multiple test cases; process until end of file.

Output Format

For each test case, output two integers: the minimum cost and the number of minimum-cost solutions. If no feasible solution exists, output $\verb!-1 -1!$. Since the number of solutions may be large, output the count modulo $(10^9+7)$.

2
  0 1 0 0 0
0 0 2 0 4 0 0
0 0 4 3 0 3 2
  0 0 0 1 0

18 1

3
    0 0 0 1 0 0 0
  0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 3 0 0 0 0
  0 0 0 0 0 0 0 0 0
    0 3 0 1 0 2 0

44 1

Hint

Explanation for Sample 2.

Constraints

• For $50\%$ of the testdata, $N \le 4$.
• For $100\%$ of the testdata, $N \le 6$.

Translated by ChatGPT 5