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 JAVA):

Solution:
import java.util.*;
import java.io.*;

public class Main {

	public static final int mod = 1000000007;

	public static int count(int k) { // count number of ones in binary
		int c = 0;
		while (k > 0) {
			k &= k - 1;
			c++;
		}
		return c;
	}

	public static String pad(String s, int n) {
		for (int i = s.length(); i < n; i++) {
			s = "0" + s;
		}
		return s;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] s;
		boolean[][] matches = new boolean[n][n];
		for (int i = 0; i < n; i++) {
			s = br.readLine().split(" ");
			for (int j = 0; j < n; j++)
				matches[i][j] = Integer.parseInt(s[j]) == 1;
		}

		int[][] dp = new int[n][(1 << n)];

		for (int i = 0; i < n; i++)
			dp[0][(1 << i)] = matches[i][0] ? 1 : 0; //last man left
	
		// i is women left, j is women bitmask
		
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < (1 << n); j++) {
				if (count(j) != i)
					continue;
				for (int k = 0; k < n; k++) { //for every possible man
					if (matches[k][i]) { //if the man and woman are compatible
						if (((1<<k) & j) == 0) { //and if the woman has not been taken in this bitmask
							dp[i][j^(1<<k)] += dp[i-1][j]; //the case where this woman is taken + current ways
							dp[i][j^(1<<k)] %= mod;
						}
					}				
				}
			}
		}
		
//		for (int i = 0; i <n; i++) {
//
//			for (int j = 0; j < (1 << n); j++) {
//				System.out.print(dp[i][j] + " ");
//			}System.out.println();
//		}
//		
		int ans = 0;
		for (int i = 0 ; i < (1<<n); i++)
			ans = ans + dp[n-1][i] % mod;
		System.out.println(ans);

	}

}