Problem C
Random Walking in a Winter Wonderland

Image by moises terrero.

Frosty the snowman likes to take random walks in the snow. Leaving his house, he can walk one block north, south, east or west at random (with equal probability). This is considered one step. Then he walks another block in a random direction, and so on. He could get virtually anywhere in his city this way. There may be many different ways to get to the same spot in the same number of steps. For example, going north, then east, then south gets to the same location as going south, then north, then east. The only places that Frosty is not allowed to walk are over a steam vent, or out of the city. Frosty takes lots of these random walks, and he wants to find out how many ways there are to get to other places in the city in a fixed number of steps. You are here to rescue him from having to walk forever to figure out the answers to his quandaries by writing a program.

Input

Input is a city map and the lenght of Frosty’s walking path. The first line contains two integers, $m$ and $n$, which specify the number of rows and columns of the map. We know that $1 \le m, n \le 30$. After this is a map description given as $m$ lines, each of which has $n$ characters. Each character represents a cell in the map, and is one of the following:

• ‘h’ – indicates Frosty’s home

• ‘o’ – indicates a place Frosty can walk

• ‘.’ – indicates a steam vent (a place where Frosty cannot go)

• ‘d’ – indicates Frosty’s destination

There is exactly one home and one destination on each map. After the map is a line with the integer $s$ ($1 \le s \le 1\, 000$) which indicates the number of steps that Frosty will take. Frosty always stays within the city, and he can walk anywhere on the map (except on steam vents) as many times as he wants.

Output

Print the number of ways that Frosty can get from his home to the destination by going on unique random walks.

3 3
ho.
odo
.o.
2

2

3 3
ho.
odo
.o.
40

107305138913280

3 3
ho.
odo
.o.
5

0