問題文
高橋君は縦 5 マス、横 5 マスの盤面に 1 から 25 までの整数を 1 つずつ書き込もうとしています。
高橋君は以下の条件をすべて満たすように整数を配置しようと考えています。
-
整数は各マスに 1 つずつ割り当てる。
-
縦または横に連続する 3 つの整数をどのように取り出しても、それらは昇順または降順になっていない。すなわち、上から i(1≦i≦5) 番目、左から j(1≦j≦5) 番目のマスに書かれた整数を ni,j としたとき、以下の 2 条件が成立する。
-
ni,j＜ni+1,j＜ni+2,j あるいは ni,j＞ni+1,j＞ni+2,j を満たす整数組 (i,j)(1≦i≦3,1≦j≦5) が存在しない。
-
ni,j＜ni,j+1＜ni,j+2 あるいは ni,j＞ni,j+1＞ni,j+2 を満たす整数組 (i,j)(1≦i≦5,1≦j≦3) が存在しない。
すでにいくつかのマスについては、どの整数を書き込むかは決まっています。あなたの課題は、上記の条件を満たすような残りの整数の配置の総数を計算することです。
入力
入力は以下の形式で標準入力から与えられる。
x1,1 x1,2 x1,3 x1,4 x1,5
x2,1 x2,2 x2,3 x2,4 x2,5
x3,1 x3,2 x3,3 x3,4 x3,5
x4,1 x4,2 x4,3 x4,4 x4,5
x5,1 x5,2 x5,3 x5,4 x5,5
- 1 行目には、5 つの整数 x1,1(0≦x1,1≦25) と x1,2(0≦x1,2≦25) と x1,3(0≦x1,3≦25) と x1,4(0≦x1,4≦25) と x1,5(0≦x1,5≦25) が空白区切りで書かれている。
- 2 行目には、5 つの整数 x2,1(0≦x2,1≦25) と x2,2(0≦x2,2≦25) と x2,3(0≦x2,3≦25) と x2,4(0≦x2,4≦25) と x2,5(0≦x2,5≦25) が空白区切りで書かれている。
- 3 行目には、5 つの整数 x3,1(0≦x3,1≦25) と x3,2(0≦x3,2≦25) と x3,3(0≦x3,3≦25) と x3,4(0≦x3,4≦25) と x3,5(0≦x3,5≦25) が空白区切りで書かれている。
- 4 行目には、5 つの整数 x4,1(0≦x4,1≦25) と x4,2(0≦x4,2≦25) と x4,3(0≦x4,3≦25) と x4,4(0≦x4,4≦25) と x4,5(0≦x4,5≦25) が空白区切りで書かれている。
- 5 行目には、5 つの整数 x5,1(0≦x5,1≦25) と x5,2(0≦x5,2≦25) と x5,3(0≦x5,3≦25) と x5,4(0≦x5,4≦25) と x5,5(0≦x5,5≦25) が空白区切りで書かれている。
上記 25 個の整数は、以下の情報を表している。
- 整数 xi,j(1≦i≦5,1≦j≦5) は上から i 番目、左から j 番目のマスに書かれる整数に関する情報である。xi,j=0 ならそのマスに書かれる整数が決まっていないことを、xi,j=0 ならそのマスに書かれる整数が xi,j であることを表す。
また、入力は以下の条件を満たす。
- 1 以上 5 以下の 4 つの整数組 i,j,k,l に関して、xi,j≧1 かつ xk,l≧1 かつ (i,j)=(k,l) ならば、xi,j=xk,l。
- xi,j=0 を満たす整数組 (i,j)(1≦i≦5,1≦j≦5) は 5 個以上存在する。
部分点
この問題には部分点が設定されている。
- データセット 1 において、すべての入力には、xi,j=0 を満たす整数組 (i,j)(1≦i≦5,1≦j≦5) が 17 個以上存在する。データセット 1 に正解した場合は、30 点が与えられる。
- 追加制約のないデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。
出力
条件を満たすような残りの整数の配置の総数を 1000000007(=1,000,000,007) で割った余りを 1 行に出力せよ。出力の末尾に改行を入れること。
入力例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
出力例1
2
- まだ書かれていない整数は 6,11,12,13,14,24 の 6 つです。以下の 2 通りが、条件を満たす配置です。
14
12
15
2
7
13
11
16
1
22
20
25
4
19
6
3
23
9
18
10
17
24
5
21
8
14
13
15
2
7
12
11
16
1
22
20
25
4
19
6
3
23
9
18
10
17
24
5
21
8
入力例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
出力例2
40320
入力例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
出力例3
0
- どのように置いても条件を満たさない場合があります。
入力例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
出力例4
1
- すでにすべての整数の配置が決まっている場合もあります。
