|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|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
Write one line to the standard output. The output should contain the power of the spell Bitaro casts.
I(1 ≤ i ≤ H).
3 4 JOIJ JIOO IIII
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