Description

n\times nn×n的01矩阵aa中，若存在四个整数$l,r,u,d(1\leq l<r\leq n,1\leq d<u\leq n)$l,r,u,d(1≤l<r≤n,1≤d<u≤n)使得a[u][l]=1a[u][l]=1且a[u][r]=1a[u][r]=1且a[d][l]=1a[d][l]=1且a[d][r]=1a[d][r]=1为真，那么a[u][l]a[u][l]、a[u][r]a[u][r]、a[d][l]a[d][l]、a[d][r]a[d][r]就构成了矩阵中的一个四环。两个四环不同当且仅当l,r,u,dl,r,u,d四个数中有最少一个不同。

现在给一个01矩阵，求矩阵中不同的四环数量

Input

第一行包含一个整数n(2\leq n\leq 1000)n(2≤n≤1000)，表示矩阵的长和宽。

接下来共nn行，每行nn个字符，组成一个矩阵aa，所有元素只由{'0','1'}组成。

Output

输出包含一个整数，表示矩阵中不同的四环的数量。

Sample Input 1

2
11
11

Sample Output 1

1

Sample Input 2

2
11
10

Sample Output 2

0

Sample Input 3

4
0110
1001
1001
0110

Sample Output 3

2

思路

用一个长度为n的数组来储存这个矩阵，每个元素存一行，

用位运算，第i行和第j行按位与，然后判断结果中1的数量n，求n的阶乘，结果即为这两行可以组成的四环数量。

最后半小时都在写读入数据的部分，我真是个废物呢😭C++太烂了