성냥개비

미르코는 토큰과 성냥개비 한 무더기를 찾았다. 그는 토큰을 $R$개의 행과 $S$개의 열로 이루어진 반듯한 직사각형 격자 모양으로 늘어놓았다. 두 토큰이 같은 행 또는 인접한 행에 있고, 같은 열 또는 인접한 열에 있으면 두 토큰은 인접하다고 한다. 따라서 각 토큰에 인접한 토큰은 최대 8개이다. 미르코는 인접한 토큰 쌍 몇 개 사이에 성냥개비를 놓았다. 성냥개비를 하나 이상 거쳐 첫 번째 토큰에서 두 번째 토큰으로 가는 경로가 있으면 두 토큰은 연결되어 있다고 한다. 미르코는 모든 토큰 쌍이 연결되고 어떤 두 성냥개비도 서로 교차하지 않도록 성냥개비를 놓았다. 아래 그림은 토큰 아홉 개와 이를 연결하는 성냥개비를 보여 준다.

성냥개비의 위치를 하나로 정해지게 기록하기 위해 각 토큰마다 4비트 수를 다음과 같이 정한다.

• 값이 1인 비트는 오른쪽 위에 인접한 토큰으로 가는 성냥개비를 나타낸다.
• 값이 2인 비트는 오른쪽에 인접한 토큰으로 가는 성냥개비를 나타낸다.
• 값이 4인 비트는 오른쪽 아래에 인접한 토큰으로 가는 성냥개비를 나타낸다.
• 값이 8인 비트는 아래에 인접한 토큰으로 가는 성냥개비를 나타낸다.

각 4비트 수를 16진수 숫자 하나로 바꾸면 성냥개비의 위치 전체를 $R \times S$ 크기의 16진수 숫자 행렬로 적을 수 있다.

미르코가 성냥개비 하나를 다른 위치로 옮기되, 옮긴 뒤에도 모든 토큰 쌍이 연결되어 있고 성냥개비끼리 교차하지 않도록 하는 방법의 수를 구하는 프로그램을 작성하시오.

방법 하나는 옮길 성냥개비 하나와 새 위치 하나의 쌍이다. 새 위치는 아직 성냥개비가 없는 인접한 토큰 쌍이어야 한다. 두 성냥개비가 교차하는 경우는 같은 단위 정사각형의 두 대각선에 놓인 경우뿐이다.

첫째 줄에 토큰 격자의 행의 수와 열의 수를 나타내는 두 정수 $R$과 $S$가 주어진다. ($2 \le R, S \le 100$)

다음 $R$개의 줄에는 각각 16진수 숫자 $S$개가 주어진다. 문자 0부터 9까지는 0부터 9까지의 수를, 문자 A부터 F까지는 10부터 15까지의 수를 나타낸다.

첫째 줄에 토큰이 모두 연결된 채로, 그리고 성냥개비끼리 교차하지 않도록 성냥개비 하나를 옮기는 방법의 수를 출력한다.