11487 - Gathering Food

冬天來臨，天氣越來越冷，許多動物採取不同的方法來適應冬天。

- 遷徙，移動到溫暖的地方。

- 很少有動物仍在冬天保持活躍。

- 冬眠，動物藉由深沉睡眠，降低體溫、心跳速度，而在秋天時準備足夠的食物以及體內脂肪。

而這題著重於第三點的例子，觀察一種特別的熊。


這種熊在一個特別的森林，將這個森林定義為 N x N 的網狀格子，每個格子只會有下列三種資訊。


'.' 空地
'#' 障礙物
[A-Z] 英文字母

森林中至少存在一個英文字母，所有字母只會存在唯一一個，如果存在有 n 個字母，這必然只會存在前 n 個字母，即當 n = 3 時，確切只會有 1 A, 1 B, 1 C。

這些字母表示當地區的食物，熊會從 'A' 開始搜集其他食物，每次只會往四個方向(上下左右)移動，由於特別的習性，會根據字母順序搜集食物，當熊到達食物所在地時，才能將食物收集起來。

計算熊收集食物的最少移動步數，以及在最少移動步數下，有多少移動方法。


// 翻譯備註，非要撿起的食物必須當做障礙物。

Input

有多組測資，每組第一行有一個整數 N (N <= 10)。

Output

對於每組測資，輸出測資組編號，如果無法搜集到所有食物，則輸出 ‘Impossible’。

反之分別輸出最短路徑長及路徑個數，輸出 mod 20437 後的結果即可。

Sample Input                             Output for Sample Input

5 A.... ####. ..B.. .#### C.DE. 2 A. .B 2 A# #B 0

Case 1: 15 1 Case 2: 2 2 Case 3: Impossible