/ 
実行時間制限: 4 sec / メモリ制限: 256 MB
問題文
クリスマスの時期が近づいてきました。あなたは友達のためにクリスマスケーキとして穴あきケーキを作ることになりました。
穴あきケーキを作るために用いるケーキ生地は R 行 C 列の長方形状であり、i (1 ≦ i ≦ R) 行 j (1 ≦ j ≦ C) 列の領域を領域 (i, j) と呼ぶことにします。領域 (i, j) を食べたとき、C_{i,j} キロカロリー得られます。また、領域 (1, 1) が左上隅、領域 (R, C) が右下隅です。
あなたはこのケーキ生地を以下の手順によって穴あきケーキに加工します。
- まず、4 つの整数 a, b, c, d (1 ≦ a ＜ b ≦ R, 1 ≦ c ＜ d ≦ C, b - a ≧ 2, d - c ≧ 2) を定めます。ケーキ生地のうち、領域 (a, c) を左上、(b, d) を右下とした長方形の部分を切り出します。
- 先の手順で切り出した部分について、端に存在しない領域 1 つ (領域 (e, f) (a+1 ≦ e ≦ b-1, c+1 ≦ f ≦ d-1) とする) を選んで削除し、残りを穴あきケーキとします。
また、穴あきケーキの摂取カロリーは、穴あきケーキを構成する領域に定められたカロリーの合計値となります。
健康志向の友達は穴あきケーキを食べることによって得られる摂取カロリーがちょうど K キロカロリーとなるようなケーキを希望しています。あなたは条件を満たす穴あきケーキとして考えられるものの総数、すなわち、上記の条件を満たす 6 つの整数 a, b, c, d, e, f の選び方が全部で何通りあるかを計算することにしました。
入力
入力は以下の形式で標準入力から与えられる。
R C K s_1 s_2 : s_R
- 1 行目には、ケーキ生地の行数 R (3 ≦ R ≦ 350)、列数 C (3 ≦ C ≦ 350) および友達が希望している摂取カロリー量 K (0 ≦ K ≦ 999,999) が空白区切りで与えられる。
- 2 行目から R 行には、ケーキ生地のカロリーに関する情報が与えられる。このうち i (1 ≦ i ≦ R) 行目では 長さ C の文字列 s_i が与えられる。s_i を構成する文字はいずれも
1から9までの数字である。s_i の左から j (1 ≦ j ≦ C) 文字目の数字は、領域 (i, j) を穴あきケーキに含めることによって増加するカロリー量 C_{i,j} に等しい。
出力
穴あきケーキとして考えられる総数を 1 行に出力せよ。出力の末尾にも改行を入れること。
入力例1
4 5 14 54311 11211 17312 11119
出力例1
2
ケーキ生地は下表のようになっています。
| 5 | 4 | 3 | 1 | 1 |
| 1 | 1 | 2 | 1 | 1 |
| 1 | 7 | 3 | 1 | 2 |
| 1 | 1 | 1 | 1 | 9 |
例えば、a = 2, b = 4, c = 1, d = 4 として切り出した場合、以下の領域が切り出されます。
| 1 | 1 | 2 | 1 |
| 1 | 7 | 3 | 1 |
| 1 | 1 | 1 | 1 |
さらに、e = 3, f = 2 として穴を開けると、穴あきケーキは以下の形状となります (* は穴を開けた場所を表す)。
| 1 | 1 | 2 | 1 |
| 1 | * | 3 | 1 |
| 1 | 1 | 1 | 1 |
このとき、摂取カロリーは、1+1+2+1+1+3+1+1+1+1+1 = 14 となり、条件を満たします。
他にも a = 1, b = 3, c = 3, d = 5, e = 2, f = 4 のときに条件を満たします。
入力例2
6 7 8 1111116 1111111 1111115 1113111 1211111 1111141
出力例2
7
穴あきケーキを構成する領域のカロリーの配置が同じでも、切り出す場所、穴を開ける場所が異なれば異なるケーキとして数えます。
入力例3
3 3 9 211 121 112
出力例3
0
条件を満たす穴あきケーキが存在しない場合もあります。
入力例4
8 8 15 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
出力例4
100