## TAP2014D - Fractal domino

**[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2014 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf ] **

A question we may ask ourselves if we have a lot of free time (or if we are mathematicians, which is practically the same thing) is the following: given a board of **N × N** square cells, in how many ways can we cover it with dominoes so that the pieces do not overlap and there are no cells left uncovered? Dominoes are rectangles composed of two adjacent square cells, and can be either horizontal (**1 × 2**) or vertical (**2 × 1**). For example, there are only two ways to cover a

**2 × 2**board, but there are

**12,988,816**ways to cover an

**8 × 8**board.

**Figure 1:** **(a)** The two ways to cover a **2 × 2** board with horizontal dominoes (left) and vertical dominoes (right);

**(b)**a possible covering of an

**8**board.

**×**8For those with even more free time, there is a variant of this question in which we consider a board with some of its cells *occupied*, so that we should count the number of coverings in which the domino pieces cover only the unoccupied cells without overlapping or leaving holes. For example, there are two ways to cover a **3 × 3** board in which the central cell is occupied, and

**75,272**ways to do so in a

**7**board.

**×**7In this problem we will turn our attention to a variant of this variant of the original question, specifically thought for those of you with too much free time. We will again consider an **N × N** board in which some cells can be occupied, but we now want to cover it using

*fractal dominoes*of order

**K**.

**Figure 2:** **(a)** A **4 × 4** board with two occupied cells;

**(b)**one of the

**89**horizontal dominoes of order one for this board;

**(c)**one of the

**52**vertical dominoes of order one for the same board;

**(d)**a covering of the board in (a) with the fractal dominoes of order one in (b) and (c).

Given an **N × N** board, a fractal domino of order

**K = 0**is a regular domino piece, i.e. a rectangle of

**1**or

**×**2**2**cells. A fractal domino piece of order

**×**1**K > 0**consists of a regular domino in which each cell is a copy of the given

**N**board, and the piece as a whole is covered by fractal dominoes of order

**×**N**K-1**.

Note that in general for **K > 1** there can be more than one fractal domino piece of order **K-1** of each type (horizontal or vertical). In this case, we assume that when using a domino piece it is chosen with uniform probability among all possible fractal domino pieces of the same type and order. In a similar fashion, if there is more than one possible covering for a given board or fractal domino, we will assume all of them are equally probable.

When covering a board with fractal dominoes of order **K** one will use a certain amount of pieces of order **K**, a larger amount of pieces of order **K-1**, an even larger amount of pieces of order **K-2**, and so on. This will go on up to the point where one uses a possibly huge amount of pieces of order zero, i.e. regular domino pieces with nothing inside. For example, in Figure 2d the board is covered with seven fractal dominoes of order one and **98** fractal dominoes of order zero.

The task in this problem is to calculate the expected proportion of fractal dominoes of order zero (i.e. regular pieces) that are vertical, if we assume that all coverings of a given board with fractal dominoes of a given order **K** are equally probable.

### Input

The first line contains an integer number **T**, the number of test cases (**1 ≤ T ≤ 200**). **T** test cases follow.

The first line of each test case contains two integers **N** and **K**, representing the size of the board and the order of the fractal dominoes that we want to use to cover it, respectively (**2 ≤ N ≤ 8** and **0 ≤ K ≤ 10 ^{9}**). The following

**N**lines contain

**N**numbers each, being the

**j**-th number in the

**i**-th line a

**1**if the cell in row

**i**and column

**j**of the board is occupied, and

**0**otherwise. The given board is not completely occupied, and it is always possible to cover it using dominoes.

### Output

For each test case, print a single line containing a rational number representing the expected proportion of fractal dominoes of order zero that are vertical, when we consider that all coverings of the given board with fractal dominoes of order **K** are equally probable. Print the result using exactly **5** decimal digits after the decimal point, rounding if necessary.

### Example

Input:11 4 2 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0

Output:0.50750

Added by: | Fidel Schaposnik |

Date: | 2014-09-29 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |

Resource: | Argentinian Programming Tournament 2014 |