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

The entire mining area contains three mines, A, B, and C, and three refineries, a, b, and c. Each triangular region can be a mine, a refinery, a mountain, or flat land. The mining administration now requires the establishment of a transportation system such that there is a road between each mine and its corresponding refinery, and the three roads do not intersect (i.e., no triangular region contains more than two roads transporting different ores). Two triangular regions are adjacent if and only if they share a common edge. A road segment can only be built between two adjacent regions, and the cost of building such a segment is 1. Note that roads cannot be built on mountains. Due to the impact of the Martian financial crisis, the mining administration wants to know the minimum cost to build such a transportation system. Furthermore, the administration wants to know how many ways there are to achieve this minimum cost.

Input

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

Following this are $6 \times N \times N$ integers, divided into $2 \times N$ lines, representing the current state of the regions in the mining area. $0$ represents flat land, $1, 2, 3$ represent the corresponding mines or refineries, and $4$ represents a mountain. (Example 1 corresponds to Figure 2). There may be multiple test cases; process until the end of the file.

Output

For each test case, output two integers representing the minimum cost and the number of ways to achieve the minimum cost. If no valid solution can be found, output -1 -1. Since the number of ways can be very large, please output the number of ways modulo $1000000007$.

Examples

Input 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 1

18 1

Input 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 2

44 1

Note

Example 2 explanation.

Constraints

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

Figure 1. The mining area divided into regular triangular regions.

Figure 2. Example 1 configuration.