시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 73 46 41 61.194%

문제

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).

Now, Bitaro has arranged one of these three types on each square. Bitaro is going to cast a spell, the power of which is determined by the arrangement of jewels, orbs and ingots. Specifically, the power equals to 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 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.

입력

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.

출력

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

제한

• 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).

3 4
JOIJ
JIOO
IIII

예제 출력 1

3

In this sample, 3 quadruplets (i, j, k, ℓ) = (1, 1, 3, 2), (2, 1, 3, 3), (2, 1, 3, 4) satisfy the condition, so you should output 3.

4 4
JJOO
JJOO
IIJO
IIIJ

17