You are given a matrix A that consists of N rows and M columns. Every number in the matrix is either zero or one. Calculate the number of such triples (i, j, h) where for all the pairs (x, y), where both x and y belong to [1; h] if y >= x, A[i+x-1][j+y-1] equals to one. Of course, the square (i, j, i+h-1, j+h-1) should be inside of this matrix. In other words, we're asking you to calculate the amount of square submatrices of a given matrix which have ones on and above their main diagonal.

Input

The first line of the input consists of two integers - N and M.

The following N lines describe the matrix. Each line consists of M characters that are either zero or one.

Output

Output should consist of a single integer - the answer to the problem.

Example

Input:
2 3
011
111

Output:
6

Scoring

Subtask 1 (9 points): 1 <= N,M <= 2000, All the numbers in the matrix are equal to one.

Subtask 2 (12 points): 1 <= N,M <= 10. 

Subtask 3 (34 points): 1 <= N,M <= 30. 

Subtask 4 (17 points): 1 <= N,M <= 150. 

Subtask 5 (28 points): 1 <= N,M <= 2000. 

The subproblem can be seen as for any given submatices its (i-1)(k-1) submatrice has to exist and (i-1)(j) has to 

that will signify that we can form a matrix by appending the extra 1 here.  obviously if the element is 0 then there is no question of having a submatrix

code

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

ll dp[3000][3000];

char str[3000];

int arr[2010][2010];

int main()

{

int t;

int n;

cin>>n;

int m;

cin>>m;

for(int i=1;i<=n;i++)

{

cin>>str;

for(int j=1;j<=m;j++)

{

 arr[i][j]=(str[j-1]-'0');

}

}

// cout<<"teaken "<<endl;

for(int i=1;i<=m;i++)

{ 

 dp[1][i]=arr[1][i];

 

}

for(int j=1;j<=n;j++)

{

  dp[j][1]=arr[j][1];

}

// cout<<"d1 "<<endl;

for(int i=2;i<=n;i++)

{

 for(int j=2;j<=m;j++)

 {

  if(arr[i][j]==1)

    dp[i][j]=1+min(dp[i-1][j-1],dp[i-1][j]);

    else

    dp[i][j]=0;

 }

}

//11cout<<"done "<<endl;

        ll ans=0;

for(int i=1;i<=n;i++)

{

for(int j=1;j<=m;j++)

{

 ans+=dp[i][j];

 }

}

cout<<ans<<endl;

return 0;

}