Strah

시간 제한1초메모리 제한256 MB

요약

'.'와 '#'으로 이루어진 N×M 격자에서 모든 '.' 부분 사각형의 개수를, 각 칸을 포함한 개수로 합산한 값을 구합니다.

난이도: 보통10점 중 7점
유형: 스택, 조합론, 구현, 수학
정답자: 아직 제출이 없습니다

문제

누구나 무언가를 두려워한다. 어떤 사람은 어둠을, 어떤 사람은 높은 곳을, 어떤 사람은 Vinnie Jones를 두려워한다(우리 모두는 Vinnie Jones를 두려워한다). 어떤 사람은 무언가를 먹기 전에 노래하는 것을 두려워한다.

두려움은 많지만, Mirko에게 가장 큰 두려움은 딸기를 심을 땅을 고르는 일이다. Mirko의 땅은 N개의 행과 M개의 열로 이루어진 행렬로 나타낼 수 있다. 행렬의 어떤 칸은 딸기를 심기에 적합하고, 어떤 칸은 적합하지 않다. 그곳에는 잡초가 자란다. Mirko는 딸기를 심기에 적합한 칸으로 완전히 채워진 직사각형 부분을 찾고 있다. 이런 직사각형을 적합한 직사각형이라고 한다. 또한 Mirko는 행렬의 모든 칸이 지닌 잠재적 가치에도 관심이 있다. 행렬의 각 칸이 지닌 잠재적 가치는 그 칸을 포함하는 적합한 직사각형의 개수로 정의된다.

Mirko는 자신의 두려움을 마주하기 힘들어하므로, 당신에게 모든 칸의 잠재적 가치의 합만 계산해 달라고 부탁한다.

입력

첫째 줄에는 땅의 크기를 나타내는 두 양의 정수 N과 M(1 ≤ N, M ≤ 2 000)이 주어진다. 다음 N개의 줄에는 각각 M개의 문자로 지형이 주어진다. 각 문자는 딸기를 심기에 적합한 칸을 나타내는 ‘.’(점)이거나 잡초를 나타내는 ‘#’이다.

출력

행렬의 모든 칸이 지닌 잠재적 가치의 합을 출력한다.

예제3

예제 1
입력
```
2 3
.#.
..#
```
예상 출력
```
8
```
예제 2
입력
```
3 3
...
...
...
```
예상 출력
```
100
```
예제 3
입력
```
3 4
..#.
#...
...#
```
예상 출력
```
40
```