There are A children in a town and Santa bought A gifts for them. But he came to know about all the pairs of which gift made which children happy. There were some gifts which made some children super happy. Santa also knew about this. Santa wanted to know among all the combinations of gifting these A gifts to A children which combinations made all A children happy or made at least one child super happy.

Given a 2D integer array B of size A*A where

B[i][j] = 1 if the jth gift does not make the ith child happy.

B[i][j] = 2 if the jth gift makes the ith child happy. B[i][j]=3 if the jth gift makes the ith child super happy.

Problem Constraints

1 <= A <= 13

Input Format

The first argument is a single integer A. The second argument is a 2D integer array B.

Output Format

Return a single integer that is among all the combinations of gifting these A gifts to A children which combinations made all A children happy or made at least one child super happy.

Example Input

Input 1

A * 2

-[[2, 2],

[2, 1] ]

Input 2:

A= 3

- [[1, 1, 3] ,[2, 2, 3], [1, 3, 3 ]]

Example Output

Output 1:-

1

Output 2:

6

Example Explanation

Explanation 1:-

Only possible combination of gifting is [2, 1]

Explanation 2:-

The possible combinations of gifting are [3, 1, 2], [3, 2, 1], [1, 2, 3], [2, 1, 3], [1, 3, 2], [2, 3, 1)

give an approach to solve this problem