给定一个 n × m 的网格,其中一些节点是黑色的,其他节点是白色的。而且,它不是一个普通的网格——网格的每个单位方块都画有对角线。
下图是一个大小为 3 × 5 的网格的示例。该网格的 4 个节点是黑色的,其他 11 个节点是白色的。
您的任务是计算给定网格上此类三角形的数量:
- 角点与白色节点匹配,面积为正;
- 所有边都沿着网格线(水平、垂直或对角线);
- 没有边包含黑色节点。
输入
第一行包含两个整数 n 和 m (2 ≤ n, m ≤ 400)。以下 n 行中的每一行都包含 m 个字符(零和一)——网格的描述。如果第 i 行中的第 j 个字符等于 0,则第 i 水平行和第 j 垂直行上的节点被涂成白色。否则,该节点将被涂成黑色。
水平线从上到下从 1 开始编号,垂直线从左到右从 1 开始编号。
输出
打印一个整数 — 所需三角形的数量。
示例
输入 #1
3 5 10000 10010 00001
输出 #1
20
输入 #2
2 2 00 00
输出 #2
4
输入 #3
2 2 11 11
输出 #3
0
注意
下图显示了红色和蓝色三角形。它们是第一个示例中所需三角形的示例。无效三角形之一被涂成绿色。这是无效的,因为并非所有边都沿着网格线。