Escape from Leng P17539

Professor William Dyer from the famous University of Miskatonic is in great danger. He has discovered and started to explore a colossal lost city in the Plateau of Leng in the Antarctic, just to realize that he is not alone: terrible creatures that colonized the Earth two billion years ago are still there! Now Prof. Dyer is running for his life, descending a hill of ice, trying to reach his plane at the bottom of the hill, with a Shoggoth pursuing him. Prof. Dyer can run downwards, never upwards, with perhaps some movements left or right. He has just the energy to make L such lateral movements slipping on the ice.

To make things worse, in the ice under his feet Prof. Dyer can see other sleeping creatures, the Old Ones, which he wisely wishes not to awake. So he decides to consider the hill as a rectangular grid, in order to leave a cautious distance of 3 cells, both horizontally and vertically, between him and every Old One during the whole path from his starting position to the plane.

[r]

To the right we can see an example. The ‘D’ indicates the position of Prof. Dyer. The ‘P’ indicates the position of the plane. In the example there are four Old Ones. The painted cells are too dangerous to pass by. For L = 1, the only escape path is the green dashed one starting to the right of Prof. Dyer. For L = 2, there is just another escape path: the blue dashed one starting to the left of Prof. Dyer. Note, Prof. Dyer will never waste energy by moving more than once horizontally on the same row. So the red dotted path is not valid.

Prof. Dyer is too terrified to find a path to escape, and he already hears the Shoggoth approaching...

Input

Input consists of several cases. Every case begins with 2 ≤ R ≤ 15 and 1 ≤ C ≤ 15, the number of rows and the number of columns of the grid, respectively, followed by the maximum number of lateral movements 0 ≤ L ≤ R. Then follow R lines with C characters each: a ‘.’ stands for an empty position; a letter ‘O’ stands for an Old One. There is exactly one ‘D’ in the first row and one ‘P’ in the last row. A special test case with R = C = L = 0 marks the end of input.

Output

Prof. Dyer would be relieved if you indicated him an escape path. But let’s be cruel. For every test case, just tell him the number of different escape paths. If there are no escape paths, print “Good bye, Professor Dyer!”.

[r]