Bitaro the Brave

Interview

Time limit1sMemory limit512 MB

Summary

Count quadruples (i, j, k, l) with i<k and j<l such that grid cells (i,j)='J', (i,l)='O', (k,j)='I'. H, W up to 3000.

Level: Medium6 of 10
Topics: Prefix sum, Array, Combinatorics
Solved: No attempts yet

Problem

Bitaro the Brave faces the Devil.

Bitaro is going to attack the Devil by arranging jewels, orbs and ingots on an H times W grid and casting a spell. The square at the i-th row (1 ≤ i ≤ H) from the top and the j-th column (1 ≤ j ≤ W) from the left is denoted by (i, j).

Bitaro has arranged one of these three types on each square. The power of the spell Bitaro is going to cast is determined by the arrangement of jewels, orbs and ingots. Specifically, the power equals the number of quadruplets of integers (i, j, k, ℓ) (1 ≤ i < k ≤ H, 1 ≤ j < ℓ ≤ W) satisfying the following condition.

Condition: Bitaro has arranged a jewel on the square (i, j), an orb on the square (i, ℓ) and an ingot on the square (k, j).

Bitaro is wondering about the power of the spell.

Write a program which, given the arrangement of jewels, orbs and ingots, calculates the power of the spell Bitaro casts.

Input

Read the following data from the standard input.

H W
S1
:
SH

Si (1 ≤ i ≤ H) is a string of length W. The item arranged on the square (i, j) (1 ≤ j ≤ W) is a jewel if the j-th character of Si is J, an orb if it is O and an ingot if it is I.

Output

Write one line to the standard output. The output should contain the power of the spell Bitaro casts.

Constraints

2 ≤ H ≤ 3 000.
2 ≤ W ≤ 3 000.
Si is a string of length W (1 ≤ i ≤ H).
Each character of Si is J, O, or I (1 ≤ i ≤ H).

Examples2

Example 1
Input
```
3 4
JOIJ
JIOO
IIII
```
Expected output
```
3
```
Example 2
Input
```
4 4
JJOO
JJOO
IIJO
IIIJ
```
Expected output
```
17
```