Problem: There are N men and N women, both numbered 1, 2, \ldots, N.

For each i, j (1 \leq i, j \leq N), the compatibility of Man i and Woman j is given as an integer a_{i, j}. If a_{i, j} = 1, Man i and Woman j are compatible; if a_{i, j} = 0, they are not.

Taro is trying to make N pairs, each consisting of a man and a woman who are compatible. Here, each man and each woman must belong to exactly one pair.

Find the number of ways in which Taro can make N pairs, modulo 10^9 + 7.

Constraints

* All values in input are integers.
* 1 \leq N \leq 21
* a_{i, j} is 0 or 1.

Input

Input is given from Standard Input in the following format:


N
a_{1, 1} \ldots a_{1, N}
:
a_{N, 1} \ldots a_{N, N}


Output

Print the number of ways in which Taro can make N pairs, modulo 10^9 + 7.

Examples

Input

3
0 1 1
1 0 1
1 1 1


Output

3


Input

4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0


Output

1


Input

1
0


Output

0


Input

21
0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0
0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1
0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0
1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0
0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1
0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1
0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0
0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1
0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1
1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1
0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1
1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1
0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1
0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0
1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0
1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0


Output

102515160

Solution (in CPP):

Solution:
#include<bits/stdc++.h> 
using namespace std;

int M=1e9+7;

int solve(vector<vector<int>>& grid){
	int n=grid.size();
	vector<int> dp(1<<n);
	dp[0]=1;
	for (int mask=0;mask<(1<<n)-1;mask++){
		int a = __builtin_popcount(mask);
		for (int b=0;b<n;b++){
			if (grid[a][b] and !(mask & (1<<b))){
				int m2=mask^(1<<b);
				dp[m2]=(dp[m2]%M+dp[mask]%M)%M;
			}
		}
	}
	return dp[(1<<n)-1];
}

signed main() {

	int N;
	cin>>N;
	vector<vector<int>> grid(N,vector<int>(N));
	for (int i=0;i<N;i++){
		for (int j=0;j<N;j++){
			cin>>grid[i][j];
		}
	}
	cout<<solve(grid)<<endl;
    return 0; 
}