#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair P; template struct LazySegmentTree{ using F=function; using G=function; using H=function; int sz; vector data; vector lazy; const F f; const G g; const H h; const Monoid e1; const OperatorMonoid e0; LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &e1, const OperatorMonoid &e0): f(f), g(g), h(h), e1(e1), e0(e0){ sz=1; while(sz v){ for(int i=0; i=0; i--) data[i]=f(data[2*i+1], data[2*i+2]); } void eval(int k, int l, int r){ if(lazy[k]!=e0){ data[k]=g(data[k], lazy[k], r-l); if(k; int main() { string s; cin>>s; int n=s.size(); int l=0; while(l=0 && s[r]=='0') r--; mint c=mint(l+1)*mint(n-r); s=s.substr(l, r-l+1); n=s.size(); auto f=[&](mint a, mint b){ return a+b; }; auto g=[&](mint a, pair p, int len){ return p.first*a+p.second*len; }; auto h=[&](pair p, pair q){ return make_pair(p.first*q.first, p.second*q.first+q.second); }; LazySegmentTree> seg(n+1, f, g, h, 0, make_pair(1, 0)); int i=0; while(s[i]=='1') i++; seg.update(0, seg.sz, make_pair(1, i)); while(i