
勇者のビ太郎は,魔王と対峙することとなった.
ビ太郎は,縦 H 行,横 W 列のマス目上に宝石 (Jewel),オーブ (Orb),金塊 (Ingot) を配置し,魔法を発動することによって魔王に攻撃をしようとしている.以下,マス目のうち上から i 行目 (1leqqileqqH),左から j 列目 (1leqqjleqqW) のマスを,マス (i,j) と表す.
ビ太郎は今,それぞれのマスにこれら 3 種類のうち 1 個を配置した.今から魔法を発動しようとしているが,この魔法の威力はマス目上の宝石,オーブ,金塊の配置によって決まる.具体的には,次の条件を満たす整数 (i,j,k,l) (1leqqi<kleqqH,1leqqj<lleqqW) の組の個数が,魔法の威力である.
条件:マス (i,j) には宝石が,マス (i,l) にはオーブが,マス (k,j) には金塊が置かれている.
ビ太郎は,この魔法の威力が気になっている.
マス目上の宝石,オーブ,金塊の配置が与えられたとき,ビ太郎が発動する魔法の威力を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
H W
S1
vdots
SH
Si (1leqqileqqH) は長さ W の文字列で,その j 文字目 (1leqqjleqqW) が J
のときはマス (i,j) に宝石が,O
のときはマス (i,j) にオーブが,I
のときはマス (i,j) に金塊が置かれていることを表す.
出力
標準出力に,魔法の威力を表す整数を 1 行で出力せよ.
制約
- 2leqqHleqq3,000.
- 2leqqWleqq3,000.
- Si は長さ W の文字列である (1leqqileqqH).
- Si の各文字は
J
,O
,I
のいずれかである (1leqqileqqH).
小課題
- (20 点) Hleqq100,Wleqq100.
- (30 点) Hleqq500,Wleqq500.
- (50 点) 追加の制約はない.
入力例 1
出力例 1
この入力例では,(i,j,k,l)=(1,1,3,2),(2,1,3,3),(2,1,3,4) の 3 個の組が条件を満たすので,答えは 3 である.
入力例 2
出力例 2