As every cow does occasionally, Bessie has lost herself in the woods! She desperately needs to get back to the barn but has no idea where to go.
The woods can be thought of as an R x C grid (1 <= R <= 5; 1 <= C <= 5). Bessie is located in the lower left corner at row 1, column 1; the barn is located in the upper right corner at in row R, column C. Each square in the grid is either empty (denoted by '.') or blocked by a tree (denoted by 'T'). Bessie's square and the barn will always be empty.
From a given square, Bessie may move to any adjacent square (one that shares a long edge with Bessie's current square) as long as it is empty. As Bessie is quite a smart cow, she never visits a square twice on the way back to the barn.
Determine the number of different ways Bessie can take that lead her from her initial position back to the barn while visiting at most K different squares (1 <= K <= R * C).

By way of example, consider this forest:
        ....
        .T..
        ....
Bessie has a number of ways to get to the upper right corner, here are all seven of them and their path lengths (the number of squares visited):
         cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f  
         bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde  
         a...  abcd  abc.  abcd  a...  a.gh  abc.  
Length:    6     6     6     8     8    10    6

* Line 1: Three space-separated integers: R, C, and K
* Lines 2..R+1: Line i+1 contains the C characters representing row R+1-i of the forest (with no spaces)

The forest is a 3 x 4 grid. A single tree sits almost in the middle, as shown. No more than six steps can be taken.

3 4 6
....
.T..
....

4

The forest is a 3 x 4 grid. A single tree sits almost in the middle, as shown. No more than six steps can be taken.
Of the several evenays to complete the traversal, only four of them touch no more than six squares along the route.