Maze Solitaire

Manao’s computer has only one game installed, called “Maze.”

In the original game, the player starts at a fixed cell in the maze and must find the exit.
The maze is a rectangle of size $N \times M$ , divided into $N \cdot M$ unit cells.

Each cell is either empty or contains a wall. The player cannot pass through wall cells.
From one empty cell, the player can move to another empty cell only if they share a side.

It is known that the maze has exactly one exit. It is also known that between any two empty cells there is exactly one simple path (i.e., the graph of empty cells is a tree).

Over time, Manao mastered the game and could always reach the exit by the shortest path (fewest cells traversed). He eventually got bored and invented a card-based variant.

The Card Variant

Manao takes a standard 52-card deck (no jokers) and assigns:

Suits to movement directions:
- Diamonds ( $D$ ) → North (up)
- Hearts ( $H$ ) → South (down)
- Clubs ( $C$ ) → West (left)
- Spades ( $S$ ) → East (right)
Ranks to step counts:
- Ace → $1$
- Number cards $2$ – $10$ → their numeric values
- Jack, Queen, King → $11$

When Manao plays a card, he must move in the corresponding direction for exactly the number of cells given by the card’s value.

If at any point he tries to move into a wall cell, the solitaire is considered broken.
The solitaire is also broken if he reaches the exit without following the shortest possible path from the start to the exit.

If Manao plays some number of cards and ends up at the exit via the shortest path, without hitting any walls, he calls the solitaire beautiful.

Two solitaires are considered different if the sequence of cards played differs in rank, suit, or order. Each physical card can be used at most once.

Task

Given the maze layout (with one start cell S and one exit cell E), determine the number of distinct beautiful solitaires Manao can deal.
Output the answer modulo $1, 000, 000, 009$ .

Constraints

$1 \leq N, M \leq 50$
The maze contains exactly one S (start) and one E (exit).
Between any two empty cells there is exactly one simple path (the empty cells form a tree).

Input Format

The first line contains an integer $T$ - the number of test cases.
Each test case starts with a line containing two integers $N$ and $M$ — the number of rows and columns in the maze.
The next $N$ lines each contain $M$ characters describing the maze:
- . — an empty cell
- X — a wall cell
- S — the starting cell
- E — the exit cell

Output Format

Output $T$ lines, one per test case.
On the $i$ -th line, output "Case #i: K", where $K$ is the number of beautiful solitaires modulo $1, 000, 000, 009$ .

Example

Input

1
9 4
.X.S
...X
.X.X
.X.X
.X.X
.X.X
.X.X
.X.X
EX..

Output

Case #1: 5

Explanation

There are exactly 5 beautiful solitaires for this maze:

AC AH 2C 7H
AC AH 2C 2H 5H
AC AH 2C 5H 2H
AC AH 2C 3H 4H
AC AH 2C 4H 3H

Here, XY denotes rank X and suit Y:

A = Ace; C = Clubs; H = Hearts.
Suits correspond to directions: Clubs → West, Hearts → South.
Each sequence follows the unique shortest path from S to E without hitting any walls, and uses each physical card at most once.