Lately, Bajtazar has become a fan of the game Carcassonne. In this game, players take turns placing square tiles with unit side lengths on a board; each new tile (except for the first one) must be connected by at least one side to a previously placed tile. Each player draws a new tile immediately after placing the previous one, so Bajtazar can plan his strategy for his next move while other players are making theirs. However, he must consider several possibilities in case one of his opponents places their tile on a square where Bajtazar wanted to place his.

On an $n \times n$ grid (Bajtazar's table has its limitations), some tiles have already been placed. Bajtazar is now waiting for the moves of his $k$ opponents. He is wondering how many possible situations he needs to prepare for, or more precisely: how many different configurations can be formed after $k$ moves are made by the players? We ignore the pictures on the tiles; configurations are considered different if there exists a square that contains a tile in one configuration but not in the other.

Input

The first line of input contains two integers $n$ and $k$ ($2 \leq n \leq 3000$, $1 \leq k \leq 4$), representing the side length of the board and the number of Bajtazar's opponents. Each of the next $n$ lines contains a description of one row of the board in the form of an $n$-letter string consisting of the characters "#" (hash) and "." (dot): the $j$-th letter of the $i$-th string represents the square in the $i$-th row and $j$-th column of the board; a dot represents an empty square, and a hash represents a square with a tile. There will be at least one tile already placed on the board, and at least $k$ empty squares.

Output

Output a single integer representing the number of different configurations that can be obtained after $k$ moves. This number should be output modulo $10^9 + 7$.

Examples

Input 1

3 2
.#.
##.
#..

Output 1

8