Come Back Home

Hansu is returning home after camp. He starts in the lower-left cell of the map, and his home is in the upper-right cell. He never visits the same cell twice, and cells marked T cannot be entered.

Given an R x C grid and an integer K, count the number of simple paths from the start cell to the home cell whose length is exactly K. The length of a path is the number of visited cells, including both the start cell and the home cell.

The first line contains three integers R (1 <= R <= 5), C (1 <= C <= 5), and K (1 <= K <= R x C).

Each of the next R lines contains a string of length C describing the map. A . cell can be entered, and a T cell cannot be entered.

Print the number of ways to reach home with distance K.