Problem D
Partition into cliques

Yan, the competitive programmer, is in a programming competition in which the prize is a trip to Russia. Yan is doing well but he does not know the solution for the following problem:

Given a undirected graph, count the number of ways to partition it such that every subset is a clique. (The value should be printed modulo $10^9+7$.)

A subset is a clique if, for every pair of vertices in the subset, there is an edge between them. Note that a subset of a single vertex is a clique. Also note that for counting partitions, order is not important in any way. More formally, two partitions are considered different if and only if there are at least two vertices that are in the same subset in one partition, but are not in the other.

Help Yan to solve the problem and win the trip to Russia!

Input

The first line of the input contains an integer $n$ the number of vertices of the graph ($1 \leq n \leq 14$), followed by $n$ lines, each with $n$ integers. The $j$-th integer in the $i$-th line is $g_{ij}$ ($0 \leq g_{ij} \leq 1$). The integer $g_{ij}$ is $1$ if there is an edge connecting the nodes $i$ and $j$, and is $0$ otherwise. $g_{ii}$ is always zero, and since the graph is undirected, $g_{ij}$ and $g_{ji}$ are equal.

Output

Print a single integer, the number of ways to partition the graph in cliques modulo $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