라틴 방진

Chris는 퍼즐을 좋아한다. 최근 그는 라틴 방진을 바탕으로 한 스도쿠 퍼즐을 알게 되었다. $k \times k$ 표에 서로 다른 원소가 정확히 $k$개 있고, 같은 행이나 같은 열에 같은 원소가 두 번 나오지 않으면 이 표를 라틴 방진이라고 한다.

예를 들어, , , 은 라틴 방진이다. 반면 , , 은 라틴 방진이 아니다.

Chris는 새로운 라틴 방진 퍼즐을 만들고 싶다. 그에게는 $n \times m$ 표 모양의 오래된 템플릿만 있다. Chris는 이 템플릿에서 연속된 라틴 방진 조각을 잘라내려 한다. 이렇게 잘라내는 방법은 몇 가지인가? 두 방법은 한쪽에는 들어 있고 다른 쪽에는 없는 칸이 하나라도 있으면 서로 다른 방법으로 본다.

첫 줄에 템플릿의 크기를 나타내는 정수 $n$과 $m$이 주어진다($1 \le n, m \le 2\,000$).

다음 $n$개 줄에는 템플릿을 나타내는 문자열 $s_i$가 주어진다. 각 문자열은 ASCII 코드가 33 이상 126 이하인 문자 $2 \cdot m$개로 이루어진다. $i$행 $j$열의 칸은 문자 $s_{i, 2 \cdot j - 1}$와 $s_{i, 2 \cdot j}$의 쌍으로 나타난다($1 \le i \le n$, $1 \le j \le m$). 두 칸의 문자 쌍이 같으면 두 칸의 원소는 같다.

템플릿에서 라틴 방진을 잘라내는 방법의 수를 정수 하나로 출력한다.

첫 번째 입력에서 $1 \times 1$ 라틴 방진을 잘라내는 방법은 20가지이고, 그 밖에 6가지 방법이 더 있다.

(a) 방법 1	(b) 방법 2	(c) 방법 3
(d) 방법 4	(e) 방법 5	(f) 방법 6