Animesh가 Malvika의 생일 선물을 사지 않다

Malvika는 생일에 구두쇠인 Animesh로부터 초콜릿 한 개조차 받지 못해 속상했다. 자신의 행동을 뉘우친 Animesh는 이 끔찍한 실수를 어떻게 만회할 수 있을지 Malvika에게 물었다. 화가 난 Malvika는 정점이 n개인 빈 그래프 H를 주고, 간선을 추가해 자신이 좋아하는 그래프로 바꾸라고 했다. Malvika는 정점이 n개이고 간선이 m개인 그래프 G를 항상 가지고 있다. Malvika는 1, 2, …, N의 순열 P가 존재해서, H에서 정점 u와 v 사이에 간선이 있는 것과 G에서 정점 P[u]와 P[v] 사이에 간선이 있는 것이 일치하면 H를 좋아한다. Animesh는 며칠을 고민한 끝에 그런 그래프를 찾아냈고, 이것이 원하던 그래프라고 말했다. 그래도 Malvika는 여전히 화가 나 있었고, 그녀가 좋아하는 그래프를 가능한 한 많이 만들어 오라고 했다. 최근 행실을 보면 Animesh가 혼자 힘으로 해결하는 데 최소 몇 년은 걸릴 것이다. Animesh가 만들어 내야 하는 그래프의 개수를 구하라. 답은 $10^9 + 7$로 나눈 나머지로 출력한다. 간선을 추가하는 두 방법 A와 B는, A에는 있고 B에는 없는 간선 (u, v)가 하나라도 있으면 서로 다른 것으로 본다. G의 인접 행렬은 n × n 행렬 A이며, 정점 i와 j 사이에 간선이 있으면 A(i, j) = 1, 없으면 A(i, j) = 0이다. 그래프는 무방향이므로 A는 대칭행렬이고, 대각선 원소는 모두 0이다. G의 각 행과 각 열에는 적어도 n - 3개의 1이 있다.

첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 그래프 G의 정점 수 n이 주어진다. 이어서 n개의 줄에 각각 n개의 문자가 주어진다. 문자는 '0' 또는 '1'이다. i번째 줄의 j번째 문자는 인접 행렬 A의 A[i][j]이다.

각 테스트 케이스마다 답을 별도의 줄에 출력한다.

T는 1 이상이다. n은 50 이하이다.

첫 번째 예제에서 G는 1과 2 사이에 간선이 있다. Animesh는 H에 1과 2 사이의 간선 하나만 추가하면 되며, 이것이 그가 만들어야 하는 유일한 그래프이다. 두 번째 예제에서 G는 1과 3 사이, 2와 3 사이에 간선이 있다. Animesh는 {{1, 3}, {2, 3}}, {{2, 1}, {3, 1}}, {{1, 2}, {3, 2}}를 만들 수 있으며, Malvika는 이 그래프들을 모두 좋아한다. 이 표기에서 {{1, 3}, {2, 3}}은 정점이 3개이고 간선이 2개인 그래프로, 1과 3 사이, 2와 3 사이에 간선이 있다는 뜻이다.