# I

### 如果你88.89分，注意要模的是10的10次方+7。

``````// Problem: 古神话
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/84844/I
// Memory Limit: 524288 MB
// Time Limit: 4000 ms
//

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(x) ((x)&(-(x)))
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define maxheap(x) priority_queue<x,vector<x>,less<x> >
#define minheap(x) priority_queue<x,vector<x>,greater<x> >
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef long long ll;
typedef unsigned long long ull;
char ch;
ull l[5005],r[5005],h[5005],k[5005],n,m,top;
ull d[5005][5005];
ull ans;
ull mod=10000000007;
int main()
{
IOS;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>ch;
if(ch=='1') d[i][j]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
{
h[j]++;
if(d[i][j]) h[j]=0;
}
top=0;
for(int i=m;i>=1;i--)
{
while(top!=0&&h[i]<=h[k[top]]) l[k[top]]=i,top--;
top++;
k[top]=i;
}
while(top) l[k[top]]=0,top--;
top=0;
for(int i=1;i<=m;i++)
{
while(top!=0&&h[i]<h[k[top]]) r[k[top]]=i,top--;
top++;
k[top]=i;
}
while(top) r[k[top]]=m+1,top--;
for(ull i=1;i<=m;i++)
{
ans+=(i-l[i])*(r[i]-i)*h[i];
}
}
cout<<ans%mod;
}
``````

hh,看到你C也是弄莫队，我写的莫队卡过了估计是数据水了()