時間制限 : sec, メモリ制限 : KB
Japanese

勇者ビ太郎(Bitaro the Brave)

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

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

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

条件:マス($i, j$) には宝石が,マス($i, l$) にはオーブが,マス($k, j$) には金塊が置かれている.

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

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

入力

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

$H$ $W$
$S_1$
:
$S_H$

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

出力

標準出力に,魔法の威力を表す整数を1 行で出力せよ.

制約

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

入出力例

入力例1

3 4
JOIJ
JIOO
IIII

出力例1

3

この入力例では,($i, j, k, l$) = (1, 1, 3, 2), (2, 1, 3, 3), (2, 1, 3, 4) の3 個の組が条件を満たすので,答えは3 である.

入力例2

4 4
JJOO
JJOO
IIJO
IIIJ

出力例2

17

クリエイティブ・コモンズ・ライセンス
情報オリンピック日本委員会作 『第18 回日本情報オリンピック(JOI 2018/2019) 本選』