한밤중 큰 눈이 내려 공원에 눈이 쌓였습니다. 공원은 n × m 크기의 직사각형 격자로 나타낼 수 있습니다. 격자의 r행 c열의 좌표는 (r, c)로 표현합니다. 각 격자 칸은 [눈이 쌓인 칸 / 눈덩이가 있는 칸 / 벽] 셋 중 하나입니다. 격자에는 크기가 1인 눈덩이 두 개만 존재합니다.

당신은 격자에 있는 눈덩이를 상하좌우로 인접한 벽이 아닌 칸으로 원하는 만큼 굴릴 수 있습니다.

눈덩이를 A칸에서 B칸으로 굴리면 B칸의 상태에 따라 다음과 같은 일이 일어납니다.

• 눈이 쌓인 칸 : 눈덩이의 크기가 1 늘어나고, B칸에 쌓여 있던 눈은 사라집니다.
• 눈이 없는 칸 : 한 번 눈덩이를 굴린 적이 있는 칸에는 눈덩이를 굴려도 크기가 커지지 않습니다.
• 다른 눈덩이가 있는 칸 : A칸의 눈덩이는 머리가 되고 B칸의 눈덩이는 몸통이 되어 눈사람이 만들어집니다. 눈사람이 된 눈덩이는 더 이상 굴릴 수 없습니다. 단, 머리가 되는 눈덩이가 몸통이 되는 눈덩이보다 크면 눈사람이 만들어지지 않고 눈덩이가 무너져 사라집니다.

• n = 4, m = 5인 격자의 예시입니다.

• (2, 2)에 있는 눈덩이를 위로 한 칸 굴리면 크기가 1 늘어납니다. (1 → 2)

• (3, 2)에 있는 눈덩이를 그림의 화살표대로 굴리면 크기가 3 늘어납니다. (1 → 4)

• 크기가 2인 눈덩이를 아래로 굴려 크기가 4인 눈덩이 위에 올리면 눈사람을 만들 수 있습니다. 한번 눈사람을 만들면 더 이상 눈덩이를 굴릴 수 없습니다.

눈덩이를 굴리는 방법에 따라 여러 가지 크기의 눈사람이 만들어질 수 있습니다. 당신은 만들 수 있는 눈사람의 종류가 얼마나 될지 알고 싶습니다. 눈사람의 머리 혹은 몸통의 크기가 하나라도 다르다면 서로 다른 종류의 눈사람으로 셉니다. (눈사람이 만들어진 위치가 달라도 머리, 몸통의 크기가 같다면 한 번만 셉니다.)

위 예시로 주어진 격자에서 만들 수 있는 눈사람의 종류는 아래 표의 12가지입니다.

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 이때, 눈덩이를 굴려 만들 수 있는 눈사람의 종류의 수를 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ grid의 세로 길이 = n ≤ 500
• 1 ≤ grid의 가로 길이 = m ≤ 500
  • grid[i][j]는 . / 알파벳 소문자 o / # 중 하나이며 (i+1, j+1) 격자칸 정보를 나타냅니다. .인 경우 눈이 쌓인 칸, o인 경우 눈덩이가 있는 칸, #인 경우 벽입니다.
  • 눈덩이가 있는 칸을 나타내는 o는 두 번 등장합니다.
• 눈사람을 만들 수 없는 경우는 주어지지 않습니다.

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

grid는 다음과 같습니다.

["##..",
 "##..",
 "##.#",
 ".oo#",
 "####"]

위 격자에서 만들 수 있는 눈사람의 (몸통 크기, 머리 크기) 종류는 다음 15가지입니다.

입출력 예 #3

grid는 다음과 같습니다.

["###########",
 "...o.....o.",
 "###########"]

위 격자에서 만들 수 있는 눈사람의 종류는 20가지입니다.

입출력 예 #4

grid는 다음과 같습니다.

["###########",
 "......o..o.",
 "###########"]

위 격자에서 만들 수 있는 눈사람의 종류는 25가지입니다.