얼음 위의 로봇

하얼빈의 얼음 조각에서 영감을 얻은 Arctic University of Robotics and Automata의 프로그래밍 팀원들은 대회를 마치고 집으로 돌아가면 자신들만의 얼음 축제를 열기로 했다. 이들은 겨울에 호수가 얼면 근처 호수에서 얼음 블록을 채취할 계획이다. 얼음 두께를 더 쉽게 관찰하려고 호수 표면 위에 직사각형 격자를 놓고, 가벼운 로봇이 칸에서 칸으로 이동하며 격자의 각 칸에서 얼음 두께를 측정하도록 했다. 격자 안의 세 지점이 “체크인” 지점으로 지정되며, 로봇은 전체 점검 여행의 4분의 1, 2분의 1, 4분의 3 지점에 도달했을 때 이 지점들에서 진행 보고를 무선으로 보내야 한다. 얼음 표면의 불필요한 마모를 피하려고 로봇은 격자의 왼쪽 아래 모서리, (행,열) 좌표로 (0,0)에서 점검 여행을 시작해 다른 모든 격자 위치를 정확히 한 번씩 방문하고 0행 1열에서 여행을 마쳐야 한다. 또한 로봇이 따를 수 있는 여행이 여러 개라면 날마다 다른 여행을 사용한다. 로봇은 한 번의 시간 단계마다 동, 서, 남, 북 네 방위 중 하나로 한 칸만 이동할 수 있다.

주어진 격자 크기와 세 체크인 지점의 순서에 대해 가능한 서로 다른 여행의 수를 구하는 프로그램을 작성해야 한다. 예를 들어 호수 표면이 3 × 6 격자로 나뉘어 있고 방문 순서대로 체크인 지점이 (2,1), (2,4), (0,4)라고 하자. 그러면 로봇은 (0,0)에서 시작해 18개 칸을 모두 방문한 뒤 (0,1)에서 끝나야 한다. 4번째 단계(= ⎣18/4⎦)에 (2,1), 9번째 단계(= ⎣18/2⎦)에 (2,4), 13번째 단계(= ⎣3×18/4⎦)에 (0,4)를 방문해야 한다. 이를 수행하는 방법은 정확히 두 가지다(Figure 8 참고). 격자 크기가 4로 나누어떨어지지 않으면 세 체크인 시각을 정할 때 버림 나눗셈을 사용한다.

Figure 8

어떤 구성에서는 유효한 여행이 전혀 없을 수도 있다. 예를 들어 4 × 3 격자에서 체크인 순서가 (2,0), (3,2), (0,2)라면 (0,0)에서 시작해 (0,1)에서 끝나는 격자 여행은 없다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스는 격자의 행과 열 수를 각각 나타내는 두 정수 m과 n이 있는 줄로 시작한다(2 ≤ m,n ≤ 8). 다음 줄에는 여섯 정수 r1, c1, r2, c2, r3, c3가 주어진다. 여기서 i = 1, 2, 3에 대해 0 ≤ ri < m이고 0 ≤ ci < n이다.

마지막 테스트 케이스 뒤에는 두 개의 0이 있는 줄이 온다.

1부터 시작하는 케이스 번호를 출력하고, 이어서 0행 0열에서 시작해 0행 1열에서 끝나며 i = 1, 2, 3에 대해 시각 ⎣ i × m × n / 4⎦에 ri행 ci열을 방문하는 가능한 여행의 수를 출력한다. 출력 형식은 예제 출력을 따른다.