Problem Description

In the year 2xyz, humanity has immigrated to Mars. Due to industrial needs, mining activities have begun on Mars. The mining area is a regular hexagon with a side length of $N$. For planning purposes, the entire mining area is divided into $6 \times N \times N$ triangular regions (as shown in Figure 1).

The mining area contains three mines for minerals $A$, $B$, and $C$, and three processing plants $a$, $b$, and $c$. Each triangular region can be a mine, a processing plant, a mountain, or flat land.

The mining authority requires the establishment of a transportation system such that there is a road between each mine and its corresponding processing plant, and these three roads do not intersect (i.e., no triangular region contains more than one road transporting different minerals). Two triangular regions are adjacent if and only if they share a common edge. Only adjacent regions can build a road segment, with a cost of $1$.

Note that roads cannot be built on mountains. Due to the financial crisis on Mars, the mining authority wants to know the minimum cost to establish such a transportation system. Additionally, they want to know how many minimum-cost solutions exist.

Input Format

The first line contains an integer $N$, indicating that the mining area is a regular hexagon with a side length of $N$.

The next $2 \times N$ lines contain $6 \times N \times N$ integers, representing the current state of the mining area. $0$ represents flat land, $1, 2, 3$ represent the corresponding mines or processing plants, and $4$ represents a mountain (Sample 1 corresponds to Figure 2).

There may be multiple sets of data; process until the end of the file.

Output Format

For each set of data, output two integers, representing the minimum cost and the number of ways to achieve this minimum cost. If no valid solution exists, output -1 -1. Since the number of solutions may be very large, output the number of solutions modulo $(10^9 + 7)$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

18

Input Sample #2

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

Output Sample #2

44

Notes

Explanation of Sample 2

Data Scale and Constraints

For $50\%$ of the data, $N \le 4$.

For $100\%$ of the data, $N \le 6$.

见题面 Input 部分

见题面 Output 部分