Problem D
Particione em cliques

Yan, o programador competitvo, está em uma competição de programação cujo prêmio é uma viagem para Rússia. Yan está indo bem porém não sabe a solução para o seguinte problema:

Dado um grafo bidirecional, responder o número de maneiras de particioná-lo tal que todo subconjunto seja um clique. (O valor deve ser impresso módulo $10^9+7$).

Um subconjunto é um clique se, para todo par de vértices do subconjunto, existe uma aresta entre eles. Note que um subconjunto de um só vértice é um clique. Note também que para contagem de partições ordem não é importante de nenhuma maneira. Mais formalmente, uma partição é diferente de outra se e somente existem pelo menos dois vértices que estão em um mesmo subconjunto em uma das partições, mas não na outra.

Ajude Yan a resolver o problema e ganhar a viagem para Rússia!

Input

A primeira linha do input contém um inteiro $n$ o número de vértices do grafo ($1 \leq n \leq 14$), seguidos de $n$ linhas, cada uma com $n$ inteiros. O $j$-ésimo inteiro na $i$-ésima linha é $g_{ij}$ ($0 \leq g_{ij} \leq 1$). O inteiro $g_{ij}$ é $1$ caso haja uma aresta ligando os nós $i$ e $j$, e é $0$ caso contrário. $g_{ii}$ é sempre zero e, como o grafo é bidirecional, $g_{ij}$ e $g_{ji}$ são iguais.

Output

Imprima um único inteiro, o número de maneiras de particionar o grafo em cliques módulo $10^9+7$.

2
0 1
1 0

2

5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 0
1 1 1 0 0
1 1 0 0 0

27