题目描述

在美丽的比特镇一共有 n 个景区，编号依次为 1 到 n，它们之间通过若干条 双向道路 连通。

Byteasar 慕名来到比特镇旅游，不过由于昂贵的门票费，他只能负担起 4 个景区 的门票费。他可以在任意景区开始游览，然后结束在任意景区。

Byteasar 的游览习惯比较特殊：
一旦他路过了一个景区，他就一定会进去参观；并且他 不会重复参观同一个景区。
因此，他想知道：有多少种可行的旅游路线，使得他 恰好参观 4 个景区？

换句话说，求图中有多少条 经过恰好 4 个不同顶点的简单路径。

输入格式

• 第一行一个整数 n，表示景区总数。
• 接下来 n 行，每行一个长度为 n 的 01 串。
• 第 i+1 行的第 j 个字符：
  • 为 1 表示景区 i 和景区 j 之间有道路；
  • 为 0 表示没有道路。

保证：

• 图是 无向图，即 (i,j) 与 (j,i) 的连通情况相同；
• 没有自环，即 (i,i)=0。

输出格式

输出一个整数，表示满足条件的路线条数。

样例

输入

4
0101
1010
0101
1010

输出

8

样例解释

这 8 条路径分别为：

• 1 -> 2 -> 3 -> 4
• 4 -> 3 -> 2 -> 1
• 2 -> 3 -> 4 -> 1
• 1 -> 4 -> 3 -> 2
• 3 -> 4 -> 1 -> 2
• 2 -> 1 -> 4 -> 3
• 4 -> 1 -> 2 -> 3
• 3 -> 2 -> 1 -> 4

注意：路径方向不同算不同路线，因此一条路径和它的反向路径会被分别统计。

数据范围

从截图可辨识到的测试点规模大致为：

可以合理认为：

1 <= n <= 1500