Banh-mi_牛客博客

https://codeforces.com/contest/1062/problem/C

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

JATC loves Banh-mi (a Vietnamese food). His affection for Banh-mi is so much that he always has it for breakfast. This morning, as usual, he buys a Banh-mi and decides to enjoy it in a special way.

First, he splits the Banh-mi into nn parts, places them on a row and numbers them from 11 through nn. For each part ii, he defines the deliciousness of the part as xi∈{0,1}xi∈{0,1}. JATC's going to eat those parts one by one. At each step, he chooses arbitrary remaining part and eats it. Suppose that part is the ii-th part then his enjoyment of the Banh-mi will increase by xixi and the deliciousness of all the remaining parts will also increase by xixi. The initial enjoyment of JATC is equal to 00.

For example, suppose the deliciousness of 33 parts are [0,1,0][0,1,0]. If JATC eats the second part then his enjoyment will become 11 and the deliciousness of remaining parts will become [1,_,1][1,_,1]. Next, if he eats the first part then his enjoyment will become 22 and the remaining parts will become [_,_,2][_,_,2]. After eating the last part, JATC's enjoyment will become 44.

However, JATC doesn't want to eat all the parts but to save some for later. He gives you qq queries, each of them consisting of two integers lili and riri. For each query, you have to let him know what is the maximum enjoyment he can get if he eats all the parts with indices in the range [li,ri][li,ri] in some order.

All the queries are independent of each other. Since the answer to the query could be very large, print it modulo 109+7109+7.

Input

The first line contains two integers nn and qq (1≤n,q≤1000001≤n,q≤100000).

The second line contains a string of nn characters, each character is either '0' or '1'. The ii-th character defines the deliciousness of the ii-th part.

Each of the following qq lines contains two integers lili and riri (1≤li≤ri≤n1≤li≤ri≤n) — the segment of the corresponding query.

Output

Print qq lines, where ii-th of them contains a single integer — the answer to the ii-th query modulo 109+7109+7.

Examples

input

output

14
3

input

output

3
1

Note

In the first example:

For query 11: One of the best ways for JATC to eats those parts is in this order: 11, 44, 33, 22.
For query 22: Both 33, 44 and 44, 33 ordering give the same answer.

In the second example, any order of eating parts leads to the same answer.

C++版本一

线段树

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long ll;
const ll MOD=1E9+7;
const int N=100000+100;
int n,q,t;
int tree[N<<2];
char str[N];
ll pow2arr[N];
void pushdown(int rt){

    tree[rt]=tree[rt<<1]+tree[rt<<1|1];

}
void updata(int l,int r,int rt,int L,int C){
    if(l==r){
        tree[rt]=C;
        return;
    }
    int m=(l+r)>>1;
    if(L<=m)   updata(l,m,rt<<1,L,C);
    else    updata(m+1,r,rt<<1|1,L,C);
    pushdown(rt);
}
int query(int l,int r,int rt,int L,int R){
    if(L<=l&&r<=R){
        return tree[rt];
    }
    int m=(l+r)>>1;
    int res=0;
    if(L<=m)   res+=query(l,m,rt<<1,L,R);
    if(m<R)    res+=query(m+1,r,rt<<1|1,L,R);
    return res;
}
void pow2(int x){
    ll res=1;
    pow2arr[0]=res;
    for(int i=1;i<=x;i++){
        res*=2;
        res%=MOD;
        pow2arr[i]=res;
        //cout << res << endl;
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    scanf("%s",str);
    for(int i=0;i<n;i++){
        t=str[i]-'0';
        if(t)
            updata(1,n,1,i+1,1);
    }
    int x,y;
    pow2(n);
    while(q--){
        scanf("%d%d",&x,&y);
        int k=y-x+1;
        int cnt=query(1,n,1,x,y);
        //cout<<cnt<<" "<<tree[1]<<endl;
        cout << pow2arr[k-cnt]*(pow2arr[cnt]-1)%MOD << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

其实某个区间与01的位置没关系只与01 个数有关，如果有x个1，y个0，直接用sum前缀和统计
那么结果就是
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;
pow是快速幂

#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;
}