Problem about Cliques#1880

Problem about Cliques

2 seconds
256 megabytes
Medium

Given an undirected, unweighted graph, your task is to determine the number of subcliques in the graph. A subclique is a subgraph that forms a complete graph. In a complete graph with vertices, there are exactly 2^V subcliques. In an empty graph with vertices, there are exactly V + 1 subcliques.

Input

The input begins with the integer (1 \leq V \leq 60)—the number of vertices in the graph.

Then follow rows with the adjacency matrix of the graph. A indicates there is no edge, and a indicates an edge is present. The main diagonal always contains zeros. The matrix is symmetric.

Output

Print the number of subcliques in the given graph.

Examples

Example 1

Loading
Loading