Problem Description

Takahashi is trying to write integers from 1 to 25 one by one on a board that consists of 5 rows and 5 columns.

Takahashi is considering placing the integers to satisfy all the following conditions:

• Each cell is assigned exactly one integer.
• No matter how you choose 3 consecutive integers vertically or horizontally, they are not in ascending or descending order. That is, when the integer written in the cell at the i-th row from the top and the j-th column from the left is denoted as \( n_{i,j} \), the following two conditions must hold:
• There is no integer pair \( (i,j) \ (1 \leq i \leq 3, 1 \leq j \leq 5) \) that satisfies \( n_{i,j} < n_{i+1,j} < n_{i+2,j} \) or \( n_{i,j} > n_{i+1,j} > n_{i+2,j} \).
• There is no integer pair \( (i,j) \ (1 \leq i \leq 5, 1 \leq j \leq 3) \) that satisfies \( n_{i,j} < n_{i,j+1} < n_{i,j+2} \) or \( n_{i,j} > n_{i,j+1} > n_{i,j+2} \).

Some cells already have decided integers. Your task is to calculate the total number of ways to arrange the remaining integers to satisfy the above conditions.

Input Format

The input is given from the standard input in the following format:

\( x_{1,1} \) \( x_{1,2} \) \( x_{1,3} \) \( x_{1,4} \) \( x_{1,5} \) \( x_{2,1} \) \( x_{2,2} \) \( x_{2,3} \) \( x_{2,4} \) \( x_{2,5} \) \( x_{3,1} \) \( x_{3,2} \) \( x_{3,3} \) \( x_{3,4} \) \( x_{3,5} \) \( x_{4,1} \) \( x_{4,2} \) \( x_{4,3} \) \( x_{4,4} \) \( x_{4,5} \) \( x_{5,1} \) \( x_{5,2} \) \( x_{5,3} \) \( x_{5,4} \) \( x_{5,5} \)

• The first line contains 5 integers \( x_{1,1} \ (0 \leq x_{1,1} \leq 25) \), \( x_{1,2} \ (0 \leq x_{1,2} \leq 25) \), \( x_{1,3} \ (0 \leq x_{1,3} \leq 25) \), \( x_{1,4} \ (0 \leq x_{1,4} \leq 25) \), and \( x_{1,5} \ (0 \leq x_{1,5} \leq 25) \) separated by spaces.
• The second line contains 5 integers \( x_{2,1} \ (0 \leq x_{2,1} \leq 25) \), \( x_{2,2} \ (0 \leq x_{2,2} \leq 25) \), \( x_{2,3} \ (0 \leq x_{2,3} \leq 25) \), \( x_{2,4} \ (0 \leq x_{2,4} \leq 25) \), and \( x_{2,5} \ (0 \leq x_{2,5} \leq 25) \) separated by spaces.
• The third line contains 5 integers \( x_{3,1} \ (0 \leq x_{3,1} \leq 25) \), \( x_{3,2} \ (0 \leq x_{3,2} \leq 25) \), \( x_{3,3} \ (0 \leq x_{3,3} \leq 25) \), \( x_{3,4} \ (0 \leq x_{3,4} \leq 25) \), and \( x_{3,5} \ (0 \leq x_{3,5} \leq 25) \) separated by spaces.
• The fourth line contains 5 integers \( x_{4,1} \ (0 \leq x_{4,1} \leq 25) \), \( x_{4,2} \ (0 \leq x_{4,2} \leq 25) \), \( x_{4,3} \ (0 \leq x_{4,3} \leq 25) \), \( x_{4,4} \ (0 \leq x_{4,4} \leq 25) \), and \( x_{4,5} \ (0 \leq x_{4,5} \leq 25) \) separated by spaces.
• The fifth line contains 5 integers \( x_{5,1} \ (0 \leq x_{5,1} \leq 25) \), \( x_{5,2} \ (0 \leq x_{5,2} \leq 25) \), \( x_{5,3} \ (0 \leq x_{5,3} \leq 25) \), \( x_{5,4} \ (0 \leq x_{5,4} \leq 25) \), and \( x_{5,5} \ (0 \leq x_{5,5} \leq 25) \) separated by spaces.

The above 25 integers represent the following information:
- The integer \( x_{i,j} \ (1 \leq i \leq 5, 1 \leq j \leq 5) \) is the information about the integer to be written in the cell at the i-th row from the top and the j-th column from the left. If \( x_{i,j} = 0 \), the integer for that cell is not decided; if \( x_{i,j} \neq 0 \), the integer for that cell is \( x_{i,j} \).

The input also satisfies the following conditions:
- For any 4 integers \( i, j, k, l \) between 1 and 5, if \( x_{i,j} \geq 1 \) and \( x_{k,l} \geq 1 \) and \( (i,j) \neq (k,l) \), then \( x_{i,j} \neq x_{k,l} \).
- There are at least 5 integer pairs \( (i,j) \ (1 \leq i \leq 5, 1 \leq j \leq 5) \) that satisfy \( x_{i,j} \neq 0 \).

Output Format

Output the total number of ways to arrange the remaining integers to satisfy the conditions, modulo \( 1000000007 \ (= 1,000,000,007) \). End the output with a newline.

Sample Input and Output

Sample Input #1

0 0 15 2 7
0 0 16 1 22
20 25 4 19 0
3 23 9 18 10
17 0 5 21 8

Sample Output #1

2

Sample Input #2

10 14 13 15 11
16 0 17 0 18
0 19 0 20 9
21 12 22 0 23
0 24 0 25 0

Sample Output #2

40320

Sample Input #3

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
0 0 0 0 0

Sample Output #3

0

Sample Input #4

1 25 2 24 3
23 4 22 5 21
6 20 7 19 8
18 9 17 10 16
11 15 12 14 13

Sample Output #4

1

Notes/Hints

Partial Points

This problem has partial points.

• For dataset 1, all inputs have at least 17 integer pairs \( (i,j) \ (1 \leq i \leq 5, 1 \leq j \leq 5) \) that satisfy \( x_{i,j} \neq 0 \). If you solve dataset 1 correctly, you will get 30 points.
• If you solve the dataset 2 without additional constraints correctly, you will get an additional 70 points.

Sample Explanation 1

• The integers not yet written are 6, 11, 12, 13, 14, 24. The following two arrangements satisfy the conditions:

14 12 15 2 7
13 11 16 1 22
0 25 4 19 6
3 23 9 18 10
17 24 5 21 8

14 13 15 2 7
12 11 16 1 22
0 25 4 19 6
3 23 9 18 10
17 24 5 21 8

Sample Explanation 2

• Any arrangement of the remaining integers satisfies the conditions.

Sample Explanation 3

• There are cases where no arrangement satisfies the conditions.

Sample Explanation 4

• There are cases where all integers are already decided.

见题面 Input 部分

见题面 Output 部分