配点: 100 点

英雄比特太郎必须面对魔王。
Bitaro 是垂直的 H 行,横 W 你试图通过将珠宝、宝珠和金锭放置在该行的方格上并激活魔法来攻击魔王。下面,从网格顶部开始 i 行目 (1 \leqq i \leqq H),从左起 j 列目 (1 \leqq j \leqq W) 表示为 (i, j) 。
Bitaro 现在每个方块上都有这些。 3 类型 放置了 1 件。我们即将施展咒语,但该咒语的威力取决于网格上宝石、球体和金块的放置情况。具体来说,满足以下条件的整数 (i, j, k, l) (1 \leqq i < k \leqq H,1 \leqq j < l \leqq W)的对数就是魔法的威力。
条件:质量 (i, j) 有珠宝,质量 (i, l) 有一个球体, (k, j) 处有一块金块。
Bitaro对这个魔法的威力感到好奇。
给定网格上宝石、球体和金块的位置,创建一个程序来查找 Bitaro 激活的魔法的力量。
入力
输入是按以下格式从标准输入给出的。
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).
小課題
- (20 点) H \leqq 100,W \leqq 100.
- (30 点) H \leqq 500,W \leqq 500.
- (50 点)没有额外的限制。
入力例 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