시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB84926321330.870%

문제

블롭 세계에는 이러한 전설이 있다.

100년 전, 천재 인간 채완이는 에너지를 글자 세 개로 저장할 수 있고, 자신이 원하는 형태로 바꿔 쓸 수 있는 "ENERGY SYNERGY MATRIX"를 개발하였다. 이후 블롭 세계의 블롭들은 에너지를 원하는 형태로 자유롭게 쓸 수 있게 되었고, 블롭 세계는 에너지 기술에서 엄청난 발전을 이룩하게 되었다.

$ESM$을 오늘 알게 된 블롭 주환이는 이 전설을 듣고 놀라 자신이 구경하던 ENERGY SYNERGY MATRIX를 살펴보았다.

"ENERGY SYNERGY MATRIX"는 문자 E, S, M으로 구성된 $N×M$ 크기의 2차원 행렬이다. 이를 줄여서 $ESM$이라고 하자.

주환이는 $ESM$을 켜려고 한다. $ESM$은 $ESM_{x1, y1} =$ E, $ESM_{x2, y2} =$ S, $ESM_{x3, y3} =$ M ($1 \leq x1 \leq x2 \leq x3 \leq N, 1 \leq y1 \leq y2 \leq y3 \leq M$)인 임의의 세 칸 $(x1, y1)$, $(x2, y2)$, $(x3, y3)$을 차례로 누르면 켜진다.

주환이는 $ESM$을 켤 수 있는 경우의 수가 궁금해졌다. 주환이를 도와 경우의 수를 구해 주자.

경우의 수가 커질 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

입력

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

다음 $N$개의 줄에 걸쳐, 각 줄마다 $M$개의 문자가 공백 없이 주어진다.

출력

주환이가 조건에 맞게 고를 수 있는 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.

제한

  • $1 \leq N, M \leq 3\,000$
  • 모든 $i, j$ $(1 \leq i \leq N, 1 \leq j \leq M)$에 대해서 $ESM_{i, j}$은 E, S, M 중 하나이다.

예제 입력 1

3 2
EM
SS
MM

예제 출력 1

3

출처

Contest > BOJ User Contest > 블롭컵 > 제1회 블롭컵 D번