勇者ビ太郎 (Bitaro the Brave)

勇者のビ太郎は，魔王と対峙することとなった．

ビ太郎は，縦 \(H\) 行，横 \(W\) 列のマス目上に宝石 (Jewel)，オーブ (Orb)，金塊 (Ingot) を配置し，魔法を発動することによって魔王に攻撃をしようとしている．以下，マス目のうち上から \(i\) 行目 (\(1 \leqq i \leqq H\))，左から \(j\) 列目 (\(1 \leqq j \leqq W\)) のマスを，マス \((i, j)\) と表す．

ビ太郎は今，それぞれのマスにこれら \(3\) 種類のうち \(1\) 個を配置した．今から魔法を発動しようとしているが，この魔法の威力はマス目上の宝石，オーブ，金塊の配置によって決まる．具体的には，次の条件を満たす整数 \((i, j, k, l)\) (\(1 \leqq i < k \leqq H\)，\(1 \leqq j < l \leqq W\)) の組の個数が，魔法の威力である．

条件：マス \((i, j)\) には宝石が，マス \((i, l)\) にはオーブが，マス \((k, j)\) には金塊が置かれている．

ビ太郎は，この魔法の威力が気になっている．

マス目上の宝石，オーブ，金塊の配置が与えられたとき，ビ太郎が発動する魔法の威力を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる．

\(H\) \(W\)
\(S_1\)
\(\vdots\)
\(S_H\)

\(S_i\) (\(1 \leqq i \leqq H\)) は長さ \(W\) の文字列で，その \(j\) 文字目 (\(1 \leqq j \leqq W\)) が J のときはマス \((i, j)\) に宝石が，O のときはマス \((i, j)\) にオーブが，I のときはマス \((i, j)\) に金塊が置かれていることを表す．

標準出力に，魔法の威力を表す整数を \(1\) 行で出力せよ．

• \(2 \leqq H \leqq 3\,000\)．
• \(2 \leqq W \leqq 3\,000\)．
• \(S_i\) は長さ \(W\) の文字列である (\(1 \leqq i \leqq H\))．
• \(S_i\) の各文字は J，O，I のいずれかである (\(1 \leqq i \leqq H\))．

1. (\(20\) 点) \(H \leqq 100\)，\(W \leqq 100\)．
2. (\(30\) 点) \(H \leqq 500\)，\(W \leqq 500\)．
3. (\(50\) 点) 追加の制約はない．

JOI 2019 · JCIOI · CC BY-SA 4.0