Animesh does not gift Malvika on her birthday

Malvika was sad because Animesh, the miser, did not buy her even a chocolate bar on her birthday. Animesh, feeling sorry about his behavior, asked Malvika how he could make up for this catastrophic mistake. Enraged, Malvika gave him an empty graph H with n vertices and asked him to add edges to it and turn it into a graph she likes. Malvika always keeps a graph G with n vertices and m edges. Malvika likes a graph H if and only if there is a permutation P of 1, 2, …, N such that vertices u and v are joined by an edge in H exactly when vertices P[u] and P[v] are joined by an edge in G. Animesh thought for days and found such a graph, and he said it was the graph she wanted. Malvika was still angry and asked him to come up with as many graphs as possible that she likes. Given his recent track record, Animesh will need at least a few years to solve this alone. Count the graphs he must come up with. Output the answer modulo $10^9 + 7$. Two ways A and B of adding edges are different if some edge (u, v) is present in A but not in B. The adjacency matrix of G is an n × n matrix A where A(i, j) = 1 if there is an edge between i and j, and A(i, j) = 0 otherwise. The graph is undirected, so A is symmetric, and its diagonal entries are all 0. Each row and each column of G has at least n - 3 ones.

The first line contains a single integer T, the number of test cases. Each test case starts with a line containing the integer n, the number of vertices in G. Then n lines follow, each containing n characters. Each character is either '0' or '1'. The j-th character of the i-th line is A[i][j], the entry of the adjacency matrix A.

For each test case, output the answer on a separate line.

T is at least 1. n is at most 50.

In the first example, G has an edge between 1 and 2. Animesh has to add only one edge between vertices 1 and 2 to H. This is the only graph he has to come up with. In the second example, G has edges {1, 3} and {2, 3}. Animesh can come up with the graphs {{1, 3}, {2, 3}}, {{2, 1}, {3, 1}}, and {{1, 2}, {3, 2}}. Malvika likes all of these graphs. In this notation, {{1, 3}, {2, 3}} is a graph with 3 vertices and 2 edges, one between 1 and 3 and one between 2 and 3.