Description
We all know that elephants today are mainly divided into two species, the African elephant and the Asian elephant. Therefore, in chess, we also have two different pieces representing them.
The African elephant is larger in size, so its attack range is also bigger. Conversely, the Asian elephant is smaller, so its attack range is smaller.
The Afircan elephants can attack pieces that are in the same row, the same column, or diagonally. In other words, an African elephant can attack pieces on the chessboard just like the queen in chess.
The Asian elephants can attack pieces that are in the same row, the same column, or exactly 2 squares away diagonally (4, 6, 8... squares away diagonally does NOT count). In other words, an elephant located at coordinates (x, y) can attack pieces on the chessboard at (x-2, y-2), (x-2, y+2), (x+2, y-2), (x+2, y+2), (x, *), and (*, y) (where * represents any number).
Given an n * n map with obstacles on some squares (the elephant cannot be placed on them), letter O represents the empty squares and letter X represents the obstacles. Please output the number of ways to place n elephants on the chessboard without attacking each other, the species type of query will represent as k.
If k = 0, the query type is African elephants, else if k = 1, the query type is Asian elephants.
For test cases 1~4, the k = 0.
For test cases 5~6, the k = 1.
Input
The first line contains two integers n and k.
1 ≤ n ≤ 10
k is either 0 or 1.
The following n lines each contain a string of length n, where each character is either letter O or X.
Output
Output the number of ways to place n elephants on the chessboard.
Note that you do NOT need to print '\n' at the end of the output.