eolymp
bolt
Try our new interface for solving problems
Problems

Задача про Клики

Задача про Клики

Time limit 2 seconds
Memory limit 256 MiB

Дан неориентированный, невзвешенный граф. Нужно найти количество подклик данного графа. Подклика — подграф, являющийся полным графом. У полного графа из V вершин подклик ровно 2^V. У пустого графа из V вершин подклик ровно V+1.

Input data

Число V (1V60) — количество вершин в графе.

Далее в V строках графа задана матрица смежности графа. 0 обозначает отсутствие ребра, соответственно 1 обозначает присутствие ребра. На главной диагонали всегда стоят нули. Матрица симметрична.

Output data

Число подклик данного графа.

Examples

Input example #1
6
011100
101100
110100
111000
000001
000010
Output example #1
19
Author Sergey Kopeliovich
Source Winter School, Kharkov, 2011, Day 5