AT_code_thanks_festival_2015_h 穴あきケーキ

[problemUrl]: https://atcoder.jp/contests/code-thanks-festival-2015-open/tasks/code_thanks_festival_2015_h クリスマスの時期が近づいてきました。あなたは友達のためにクリスマスケーキとして穴あきケーキを作ることになりました。 穴あきケーキを作るために用いるケーキ生地は $ 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 $ 行に出力せよ。出力の末尾にも改行を入れること。

### Sample Explanation 1 ケーキ生地は下表のようになっています。 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 $ のときに条件を満たします。 ### Sample Explanation 2 穴あきケーキを構成する領域のカロリーの配置が同じでも、切り出す場所、穴を開ける場所が異なれば異なるケーキとして数えます。 ### Sample Explanation 3 条件を満たす穴あきケーキが存在しない場合もあります。