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^{9}.

Public test cases

**Input**

1 2 *K 1 2 NK 2 2 ** *K 3 3 KK* K** **N 3 7 NK***KK KK*NKKK KKKKKKN

**Output**

2 4 0 10 7

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++