该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

灯光设计师正在为舞台安装灯光装置，该灯光装置由一个 N×N 的光控矩阵组成。矩阵中的每个单元代表一个独立的灯光模块，模块的状态用数字表示：1 表示该模块亮起，0 表示熄灭。为了营造出独特的光影效果，设计师计划在矩阵中选出一个矩形区域，要求如下：

1. 矩形区域必须至少包含两行和两列（即矩形的长和宽都至少为 2）。
2. 矩形区域的四个角所对应的灯光模块必须全部亮起（即对应的数字均为 1）。
3. 选出的矩形的长、宽必须和灯光装置的长、宽平行。

你的任务是计算，在给定的光控矩阵中，有多少种不同的矩形区域能满足上述要求，从而实现预期的灯光效果。

输入格式

第一行包含一个整数 N，表示光控矩阵的大小为 N×N。

接下来 N 行，每行包含一个长度为 N 的字符串，由字符 0 和 1 组成，分别表示对应行中各个灯光模块的状态。

输出格式

输出一个整数，表示满足条件的矩形区域的总数。

样例输入输出

样例 1

• 样例输入 1：

3
011
101
111

• 样例输出 1：

2

样例 2

• 样例输入 2：

4
1101
1011
1111
1111

• 样例输出 2：

19

Hint

样例 1 解释

对于本样例，有 2 种符合题意的矩形构造方案：

1. 选择四个角分别为 (行1，列2)=1、(行1，列3)=1、(行3，列2)=1、(行3，列3)=1，符合要求。
2. 选择四个角分别为 (行2，列1)=1、(行2，列3)=1、(行3，列1)=1、(行3，列3)=1，符合要求。

其他组合均不满足条件，因此总方案数为 2。

数据范围

• 对于 50% 的数据，满足：1≤N≤100。
• 对于 100% 的数据，满足：1≤N≤300。