Checkers

In this problem you are given a (n, n) checkerboard with many black checker pieces and only one white. You have to calculate the number on different paths for the white piece to become a king (reach the top board row). You can assume that only white piece is moving, all black pieces are always standing still on their positions. All checkers moving rules (for the white piece) are applied:

Target cell must be free.
From position (x, y) checker can move only forward by one of diagonals to position (x + 1, y + 1) or (x − 1, y + 1).
If cell (x +1, y +1) or (x−1, y +1) is occupied by enemy piece it can jump over to cell (x+2, y +2) or (x − 2, y + 2) respectively.

Input

The number of tests T (T ≤ 100) is given on the first line. Each test starts with integer N (1 ≤ N ≤ 100) the board size. Next, N lines follow with N characters each describing the board itself. On the board ‘W’ stands for white piece, ‘B’ for black one and ‘.’ for unoccupied cell. There will be only one white piece in each test.

Output

For each test case output a single line ‘Case T : S’. Where T is the test case number (starting from

and S number of paths for the white piece to become a king. As this number can be huge, output it modulo 1000007.

#11957Checkers

Input

Output