모자이크

직사각형 격자 위에 검은 타일을 붙여 만드는 모자이크를 생각한다. 격자의 배경은 흰색이고, 각 칸에는 검은 정사각형 타일 하나가 놓이거나, 검은 삼각형 타일 하나가 놓이거나, 아무것도 놓이지 않아 칸 전체가 흰색으로 남는다. 삼각형 타일은 정사각형 칸을 대각선으로 자른 직각이등변삼각형이고, 직각인 꼭짓점이 칸의 네 꼭짓점 가운데 어디에 오는지에 따라 네 가지 방향이 있다.

그림 1: 모자이크의 예

그림 2: 삼각형 타일의 네 가지 방향

모자이크는 흰색으로 남은 영역이 모두 직사각형이 되도록 만든다. 이 직사각형은 격자와 나란할 수도 있고 45도 기울어져 있을 수도 있다.

작가는 검은 정사각형을 모두 놓는 것으로 작업을 시작하고, 남은 검은 삼각형은 조수가 채워 넣는다. 조수가 의도한 모양을 그대로 완성하도록, 작가는 일부 검은 정사각형에 숫자를 적어 그 정사각형과 변을 맞대는 검은 삼각형의 개수를 지정한다. 이웃한 칸의 삼각형이 검은 정사각형과 변을 맞대려면 두 칸의 공통 변 전체를 덮어야 한다. 숫자가 적히지 않은 검은 정사각형은 변을 맞대는 삼각형이 몇 개든 상관없다. 작가는 모자이크가 하나로 정해질 만큼 숫자를 충분히 적는다.

그림 3: 그림 1의 모자이크를 유일하게 정하는 시작 배치

시작 배치가 주어질 때, 모자이크를 완성하는 데 쓰이는 삼각형의 개수를 구하라.

이런 모자이크는 니코리의 퍼즐 샤카샤카에서 착안했다.

입력은 테스트 케이스 하나로 이루어진다.

첫 줄에 모자이크의 너비 $W$와 높이 $H$가 주어진다 ($1 \le W \le 24$, $1 \le H \le 18$).

이어서 $H$개의 줄에 각각 $W$개의 문자가 주어진다. 문자 0, 1, 2, 3, 4는 변을 맞대는 검은 삼각형의 개수가 그 숫자로 지정된 검은 정사각형이고, 문자 *는 그런 제약이 없는 검은 정사각형이다. 나머지 위치는 모두 .이며, 비워 두거나 검은 삼각형 하나로 덮는다.

입력은 유효한 모자이크를 정확히 하나만 정하도록 주어진다.

모자이크에 쓰인 삼각형의 개수를 출력한다.