可卿听戏 2828

Time Limit: 1 s Memory Limit: 256 MB

Submission：234 AC：52 Score：0

Description

红楼梦正册判词曾评价秦可卿：“ 漫言不肖皆荣出，造衅开端实在宁”，其鲜艳妩媚，有似乎宝钗，风流袅娜，行事温柔平和，则又如林黛玉。

这一天秦可卿和金陵十二钗其他人一起去戏院听戏，她发现戏院的观众席大约是一个$n×n$的正方形，有些人听得入神，面露悦色，有些人则不然，面露难色，她把认为戏曲好听的人的满意度设为1，把认为戏曲不好听的人的满意度设为0，那么这个观众席可以看做一个$n×n$的01矩阵，由于在同一个家族，第$i$行$j$列的观众和第$j$行第$i$列的观众的满意度一致，她认为这个戏曲的观众满意度为这个矩阵的转置乘这个矩阵所构成的矩阵的所有元素和，现在她面对一个庞大的观众席，请你帮她计算这个戏曲的观众满意度。

Input

输入共包含$n+1$行,第一行包含一个数字$n（n≤1000)$，表示矩阵$A$是一个$n×n$的矩阵,我们用一个矩阵$A$表示观众席，剩下包括$n$行，每行包括$n$个数字，第i行的第j个数字为0或1，即矩阵$A$的元素$a_{ij}$,表示坐在第$i$行第$j$列的观众对该戏曲的满意度（题目保证矩阵$A$是一个对称矩阵）。

Output

输出仅一个数字，即矩阵$A^T*A$的元素和，表示该戏曲的观众满意度。

数据保证$2≤n≤1000$, $0≤a_{ij}≤1$ 。

Samples

input

2 0 1 1 0

output

input

4 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0

output

Hint

对称矩阵：

对称矩阵（Symmetric Matrices）是指以主对角线为对称轴，各元素对应相等的矩阵。

矩阵转置：

设$A$为$m×n$阶矩阵（即$m$行$n$列），第$i$行$j $列的元素是$a(i,j)$，即：$A = (a_{ij})_{m×n}$

把$m×n$矩阵$A$的行换成同序数的列得到一个$n×m$矩阵，此矩阵叫做$A$的转置矩阵，记做$A^T$

矩阵乘法：

设$A$为$m×p$的矩阵，$B$为$p×n$的矩阵，那么称$m×n$的矩阵$C$为矩阵$A$与$B$的乘积，记作$C=AB$ ，其中矩阵$C$中的第$i$行第$j$列元素可以表示为：

$(AB)_{ij} = \sum_{k=1}^p a_{ik}b_{kj} = a_{i1}b_{1j} + a_{i2}b_{2j}+……+a_{ip}b_{pj}$