11957 - Checkers

給定一個 n x n 大小的棋盤，棋盤上有一個白子與許多黑子，請你計算白子移動到最上方一列的所有可能路徑總數，只有白子可以移動，黑子永遠停留在原處，白子移動的規則如下：

• 移動到的目標位置必須是空的。
• 位於(x, y)的白子只能向前移動對角的一格，即移動到(x+1, y+1), 或(x-1, y+1)。
• 若在位置(x+1, y+1), (x-1, y+1)上有棋子存在，請跨過移動到(x+2, y+2), 或(x-2, y+2)的位置。
  

INPUT

輸入資料的第一列有一整數T(T <= 100)表示測試資料的組數。每組資料的一開始給定一整數N(1 <= N <= 100)表示棋盤的大小，接下來的N列每列有N個字元表示棋盤的佈局，其中W表示白子，B表示黑子，. 表示空的位置。每組資料只會有一個白子。

OUTPUT

請每輸測試資料輸出格式："Case T: S"，其中T表示測試資料編號(由1開始)，S表示白子移動到最上方一列的可能路徑總數，由於其值可能極大，請你取除以1000007的餘數。

SAMPLE INPUT

2
4
....
....
....
..W.
8
.B.B.B..
........
........
..B.....
........
..B.....
.W......
........

SAMPLE OUTPUT

Case 1: 5
Case 2: 1

---

原文出處