1098 - Robots on Ice

這題的靈感來自於哈爾濱的冰雕節，在參賽隊伍回國前，北極大學(Arctic University) 的機器人將會帶領程式比賽的隊伍參觀這場慶典，他們打算從冬季結冰的湖水得到巨大的冰塊，為了監視脆弱的冰層，他們將湖畫分成網格狀，而讓機器人在湖面上運行檢查工作。

檢查工作中，將會有 3 個重要的 check-in 報到點，必須在此以無線電回報工作進度，而這三個點分別在路程的 1/4, 2/4, 3/4 的位置。為了避免與冰層表面不必要的摩擦，機器人打算從左下角 (0, 0) 出發，經過所有格子一次後，最後到 (0, 1)。如果有多種走法，而機器人盡可能每天使用不同路徑，而機器人一次只能移動四個方向一步(東西南北)。


寫一個程式，根據不同的網格大小，以及給定 3 個 check-in 點，計算有多少不同路徑種數。

例如：有一個網格 3 x 6，3 個 check-in 點順序位在 (2, 1) (2, 4) (0, 4)，機器人一開始一定在 (0, 0) 出後，經過 18 個格子後，停在 (0, 1)。而會在第 4 ( = floor(18/4)) 步走到 (2, 1)，第 9 ( = floor(2*18/4)) 步走到 (2, 4)，第 13 ( = floor(3x18/4)) 步走到 (0, 4)。

如下圖表示將會只有兩種方式：

也許會存在沒有任何的合法路徑，如 4 x 3 網格，check-in 點分別在 (2,0), (3,2), (0,2)。

Input 

輸入有多組測資，每組第一行會有兩個整數  2 <= m, n <= 8，分別表示 行(row)與列(column)。而接下來會有 6 個整數 r₁, c₁, r₂, c₂,  r₃, c₃,
(0<= r_i < m , 0 <= c_i < n for i = 1, 2, 3)
最後一組 m = n = 0  結束程式。

Output 

對於每組測資，輸出測資組編號，以及其可能的路徑總數。

並且在指定步數時抵達報到點。

$$\left \lfloor i*m*n/4 \right \rfloor \text{for i = 1, 2,3 }$$

Sample Input 

3 6 
2 1 2 4 0 4 
4 3 
2 0 3 2 0 2 
0 0

Sample Output 

Case 1: 2 
Case 2: 0