Problem Description

Bitaro the Brave is facing the Demon King.

Bitaro has placed jewels (Jewel), orbs (Orb), and ingots (Ingot) on a grid of $ H $ rows and $ W $ columns to activate a magic attack against the Demon King. Here, the grid cell in the $ i $th row ($1 \leq i \leq H$) and $ j $th column ($1 \leq j \leq W$) is denoted as cell $ (i, j) $.

Bitaro has placed one of these three items in each cell. The power of the magic he is about to activate depends on the arrangement of jewels, orbs, and ingots on the grid. Specifically, the power of the magic is determined by the number of tuples of integers $ (i, j, k, l) $ ($1 \leq i < k \leq H$, $1 \leq j < l \leq W$) that satisfy the following condition:

Condition: The cell $ (i, j) $ contains a jewel, the cell $ (i, l) $ contains an orb, and the cell $ (k, j) $ contains an ingot.

Bitaro is curious about the power of this magic.

Given the arrangement of jewels, orbs, and ingots on the grid, write a program to determine the power of the magic Bitaro will activate.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ S_1 $ $\vdots$ $ S_H $

$ S_i $ ($1 \leq i \leq H$) is a string of length $ W $, where the $ j $th character ($1 \leq j \leq W$) is J if the cell $ (i, j) $ contains a jewel, O if the cell $ (i, j) $ contains an orb, and I if the cell $ (i, j) $ contains an ingot.

Output Format

Output the power of the magic as an integer on a single line to the standard output.

Sample Input and Output

Sample Input #1

3 4
JOIJ
JIOO
IIII

Sample Output #1

3

Sample Input #2

4 4
JJOO
JJOO
IIJO
IIIJ

Sample Output #2

17

Notes/Hints

Constraints

• $2 \leq H \leq 3,000$.
• $2 \leq W \leq 3,000$.
• $ S_i $ is a string of length $ W $ ($1 \leq i \leq H$).
• Each character of $ S_i $ is either J, O, or I ($1 \leq i \leq H$).

Subtasks

1. ($ 20 $ points) $H \leq 100$, $W \leq 100$.
2. ($ 30 $ points) $H \leq 500$, $W \leq 500$.
3. ($ 50 $ points) No additional constraints.

Sample Explanation 1

In this input example, there are $ 3 $ tuples $ (i, j, k, l) = (1, 1, 3, 2), (2, 1, 3, 3), (2, 1, 3, 4) $ that satisfy the condition, so the answer is $ 3 $.

见题面 Input 部分

见题面 Output 部分