C. Banh-mi

Subject Meaning

Give you a string of n characters (0 or 1). When you go to a certain position, all the remaining positions are added with the number of that position. Query the l, r intervals Q times.
After the operation, what is the final sum? Take the model for 1e9 + 7?

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e9+7;
ll sum[1000005];
ll pow(ll a,ll b,ll n){
    ll ans=1;
    ll base=a;
    while(b){
        if(b&1) ans=ans*base%n;
        base=base*base%n;
        b>>=1;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,q;
    char s[1000005];
    //freopen("in.txt","r",stdin);
    while(cin>>n>>q){
        cin>>s+1;
        memset(sum,0,sizeof(sum));
       for(int i=1;i<=n;i++)
        if(s[i]=='1') sum[i]=sum[i-1]+1;
        else sum[i]=sum[i-1];
        int l,r;
        while(q--){
            ll ans=0;
            cin>>l>>r;
            ans=pow(2ll,sum[r]-sum[l-1],inf)-1;
            ans=(ans+(ans*(pow(2ll,r-l+1+sum[l-1]-sum[r],inf)-1))%inf)%inf;
            cout<<ans<<endl;
           }
    }
    return 0;
}