AT_joi2019ho_a.勇者ビ太郎 (Bitaro the Brave)

勇者比太郎即将与魔王对峙。

比太郎在一个高 $H$ 行、宽 $W$ 列的格子上，分别放置了宝石（Jewel）、宝珠（Orb）、金块（Ingot），并打算通过发动魔法来攻击魔王。下面，将从上往下第 $i$ 行（$1 \leq i \leq H$）、从左往右第 $j$ 列（$1 \leq j \leq W$）的格子记作格子 $(i, j)$。

比太郎已经在每个格子上放置了上述三种物品中的一种。现在他准备发动魔法，而这次魔法的威力取决于格子上宝石、宝珠和金块的分布。具体来说，满足以下条件的整数四元组 $(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$
$\vdots$
$S_H$

$S_i$（$1 \leq i \leq H$）是长度为 $W$ 的字符串，第 $j$ 个字符（$1 \leq j \leq W$）为 J 时表示格子 $(i, j)$ 上放有宝石，为 O 时表示放有宝珠，为 I 时表示放有金块。

输出一个整数，表示魔法的威力。

限制

• $2 \leq H \leq 3000$。
• $2 \leq W \leq 3000$。
• $S_i$ 是长度为 $W$ 的字符串（$1 \leq i \leq H$）。
• $S_i$ 的每个字符都是 J、O、I 之一（$1 \leq i \leq H$）。

子任务

1. （20 分）$H \leq 100$，$W \leq 100$。
2. （30 分）$H \leq 500$，$W \leq 500$。
3. （50 分）无额外限制。

样例解释 1

在这个输入样例中，满足条件的 $(i, j, k, l) = (1, 1, 3, 2), (2, 1, 3, 3), (2, 1, 3, 4)$ 共 $3$ 组，因此答案为 $3$。

由 ChatGPT 4.1 翻译