Escape from the board P18760

Consider an n × m chess board. Initially you are at the lower-right corner, that is, at the position (n − 1, m − 1). Your goal is to get out of the board. There are some prohibited cells, marked with asterisks. The allowed cells have a ‘K’ or an ‘N’. When you are on a ‘K’, you can move like a chess king. When you are on an ‘N’, you can move like a chess knight. Moreover, you cannot make any move that increments the current row or column. In how many ways can you leave the board?

Input

Input consists of several cases. Every case begins with two natural numbers n and m, both between 1 and 12. Follow n lines with m characters each, which can be an asterisk, a ‘K’ or an ‘N’. The lower-right corner never has an asterisk.

Output

For every case, print the number of ways to leave the board. This number is always smaller than 10⁹.