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 翻译