Banner(横断幕) - joi2011-day1

時間制限: 1.5秒

メモリ制限: 64MB

20XX 年，ついに IOI が JOI 国で開催されることになった． JOI 国ではこれを祝い，街中に歓迎の横断幕 (banner) をかけることにした．JOI 国では，図のように，東西方向に走る H 本の道路と，南北方向に走る W 本の道路が碁盤目状に通っている．東西方向に走る道路と南北方向に走る道路が交わるところを交差点と呼ぶ．北から a 番目，西から b 番目の交差点を (a，b) で表す．

各交差点にはそれぞれ柱が 1 本ずつ立っている．JOI 国には国を象徴する色が黒色・灰色・白色の 3 色あり，各柱はこの 3 色のうちのどれか 1 色で塗られている．

図: JOI 国の図( H = 3, W = 4 の場合)．図の上が北，左が西に対応する．

横断幕はこれらの柱を支柱としてかけることができる．ただし，横断幕が道路でないところを通っていると邪魔になってしまう．そこで，交差点に立っているこれらの柱のうち，「各辺がいずれかの道路と平行であるような長方形」の 4 頂点となっているような異なる 4 本の柱を選び，その周囲に横断幕をかける．さらに，このとき選ぶ 4 本の柱に黒色の柱・灰色の柱・白色の柱がそれぞれ 1 つ以上含まれているようにしたい．

このような 4 本の柱の選び方は何通りあるだろうか．

課題

H，W と，JOI 国に立っている柱の色の情報が与えられたとき，4 本の柱の選び方の数を出力するプログラムを作成せよ．

制限

`2 \leq H \leq 400`	東西に走る道路の本数
`2 \leq W \leq 400`	南北に走る道路の本数

入力

標準入力から以下の入力を読み込め．

1 行目には整数 H, W が空白を区切りとして書かれている．
続く H 行には，JOI 国の交差点に立っている柱の色の情報が書かれている．i + 1 行目 (1 \leq i \leq H) には，0, 1, 2 いずれかの整数が W 個空白区切りで書かれている．i + 1 行目の j 番目に書かれている整数が 0 なら，交差点 (i, j) に立っている柱が黒色であることを表し，同様に，書かれている整数が 1 なら灰色，2 なら白色であることを表す．

出力

標準出力に，4 本の柱の選び方の数を 1 行で出力せよ．

採点基準

採点用データのうち，配点の 40% 分については，H \leq 100 かつ W \leq 100 を満たす．

入出力の例

入力例	出力例
`3 4 0 1 0 2 1 2 0 1 0 0 2 1`	`12`

この入力例では，4 本の柱の選び方として

(1, 1), (2, 1), (2, 2), (1, 2)
(1, 1), (2, 1), (2, 4), (1, 4)
(1, 2), (2, 2), (2, 3), (1, 3)
(1, 3), (2, 3), (2, 4), (1, 4)
(1, 1), (3, 1), (3, 4), (1, 4)
(1, 2), (3, 2), (3, 3), (1, 3)
(1, 2), (3, 2), (3, 4), (1, 4)
(1, 3), (3, 3), (3, 4), (1, 4)
(2, 1), (3, 1), (3, 2), (2, 2)
(2, 1), (3, 1), (3, 3), (2, 3)
(2, 2), (3, 2), (3, 4), (2, 4)
(2, 3), (3, 3), (3, 4), (2, 4)
の 12 通りが存在するので 12 を出力する．