仓鼠窝

题目描述

萌萌哒的Created equal是一只小仓鼠,小仓鼠自然有仓鼠窝啦。 仓鼠窝是一个由n\*m个格子组成的行数为n、列数为m的矩阵。小仓鼠现在想要知道,这个矩阵中有多少个子矩阵!(实际上就是有多少个子长方形嘛。)比如说有一个2\*3的矩阵,那么1\*1的子矩阵有6个,1\*2的子矩阵有4个,1\*3的子矩阵有2个,2\*1的子矩阵有3个,2\*2的子矩阵有2个,2\*3的子矩阵有1个,所以子矩阵共有6+4+2+3+2+1=18个。 可是仓鼠窝中有的格子被破坏了。现在小仓鼠想要知道,有多少个内部不含被破坏的格子的子矩阵!

输入输出格式

输入格式


第一行两个正整数n和m,分别表示仓鼠窝的行数n、列数m。 接下来n行,每行m个数,每个数代表对应的格子,非0即1。若为0,表示这个格子被破坏;反之代表这个格子是完好无损的。

输出格式


仅一个正整数,表示未被破坏的子矩阵的个数。

输入输出样例

输入样例 #1

3 4
1 1 1 1
1 0 1 1
1 1 0 1

输出样例 #1

26

说明

\_\_本题时限2s,内存限制256M,因新评测机速度较为接近NOIP评测机速度,请注意常数问题带来的影响。\_\_ ```cpp No n= m= 备注 1 2 2 无 2 3 3 无 3 5 5 无 4 10 10 无 5 2000 2000 所有格子均未被破坏 6 3000 3000 所有格子均未被破坏 7 2500 3000 有且仅有一个格子被破坏 8 3000 2500 有且仅有一个格子被破坏 9 200 200 无 10 500 500 无 11 500 500 无 12 500 500 无 13 1000 1000 无 14 1000 1000 无 15 1000 1500 无 16 2500 2500 无 17 2500 3000 无 18 3000 2500 无 19 3000 3000 无 20 3000 3000 无 ```