The pasture and farm are on an N×NN×N grid (2≤N≤502≤N≤50), with her pasture in the top-left corner and the barn in the bottom-right corner. Bessie wants to get home as soon as possible, so she will only walk down and to the right. There are haybales in some locations that Bessie cannot walk through; she must walk around them.

Bessie is feeling a little tired today, so she wants to change the direction she walks at most KK times (1≤K≤31≤K≤3) .

How many distinct paths can Bessie walk from her favorite pasture to the barn? Two paths are distinct if Bessie walks in a square in one path but not in the other.

SAMPLE INPUT:

7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...

SAMPLE OUTPUT:

2
4
6
2
0
0
6

We'll denote Bessie's possible paths as strings of D's and R's, indicating that Bessie moved either down or right, respectively.

In the first sub-test case, Bessie's two possible walks are DDRR and RRDD.

In the second sub-test case, Bessie's four possible walks are DDRR, DRRD, RDDR, and RRDD.

In the third sub-test case, Bessie's six possible walks are DDRR, DRDR, DRRD, RDDR, RDRD, and RRDD.

In the fourth sub-test case, Bessie's two possible walks are DDRR and RRDD.

In the fifth and sixth sub-test cases, it is impossible for Bessie to walk back to the barn.

In the seventh sub-test case, Bessie's six possible walks are DDRDRR, DDRRDR, DDRRRD, RRDDDR, RRDDRD, and RRDRDD.

Problem credits: Nick Wu