용감한 Bitaro
면접 대비시간 제한1초메모리 제한512 MB
i<k이고 j<l인 네 칸 (i,j)는 J, (i,l)는 O, (k,j)는 I인 조합의 개수를 센다. H, W는 최대 3000이다.
문제
용감한 Bitaro가 악마에 맞선다.
Bitaro는 H행 W열 격자에 보석, 구슬, 주괴를 배치하고 주문을 외워 악마를 공격하려 한다. 위에서 i번째 행(1 ≤ i ≤ H)과 왼쪽에서 j번째 열(1 ≤ j ≤ W)에 있는 칸을 (i, j)로 나타낸다.
Bitaro는 각 칸에 세 종류 중 하나를 배치했다. Bitaro가 외울 주문의 위력은 보석, 구슬, 주괴의 배치로 정해진다. 구체적으로 위력은 다음 조건을 만족하는 정수 네 개의 쌍 (i, j, k, ℓ) (1 ≤ i < k ≤ H, 1 ≤ j < ℓ ≤ W)의 개수와 같다.
조건: Bitaro는 칸 (i, j)에 보석을, 칸 (i, ℓ)에 구슬을, 칸 (k, j)에 주괴를 배치했다.
Bitaro는 주문의 위력이 궁금해졌다.
보석, 구슬, 주괴의 배치가 주어질 때, Bitaro가 외우는 주문의 위력을 계산하는 프로그램을 작성하라.
입력
다음 데이터를 표준 입력에서 읽는다.
H W
S1
:
SH
Si (1 ≤ i ≤ H)는 길이 W인 문자열이다. 칸 (i, j) (1 ≤ j ≤ W)에 배치된 물건은 Si의 j번째 문자가 J이면 보석, O이면 구슬, I이면 주괴이다.
출력
표준 출력에 한 줄을 쓴다. 출력에는 Bitaro가 외우는 주문의 위력이 들어가야 한다.
제한
- 2 ≤ H ≤ 3 000.
- 2 ≤ W ≤ 3 000.
- Si는 길이 W인 문자열이다 (1 ≤ i ≤ H).
- Si의 각 문자는
J,O,I중 하나이다 (1 ≤ i ≤ H).