Note the unusual memory limit.

There are $N$ humans and $N$ jobs. If the $i$-th human wants to do the $j$-th job, $A_{i,j}=1$, otherwise $A_{i,j}=0$. Find the number of ways to assign each job to exactly one human such that every human does a job the human wants, modulo $10^9+7$.

Input

The first line of input contains an integer $N$. The following $N$ lines of input contains $N$ integers each. The $j$-th integer on the $i$-th following line denotes $A_{i,j}$.

Output

Output a single integer, the answer modulo $10^9 + 7$.

Constraints

$1 \le N \le 21$
$0 \le A_{i,j} \le 1$