#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
const int N=5e5+5;
int n,q,l,r,x;
string s;
struct node{
  int l,r,maxn,minn;
}t[4*N];
int s0[N],s1[N];
int p[N],idx=0,max_pos,min_pos,sum0;

int read(){
  int w=0;bool f=0;
  char ch=getchar();
  while(!isdigit(ch)){if(w=='-') f=1;ch=getchar();}
  while(isdigit(ch)){w=(w<<3)+(w<<1)+ch-'0';ch=getchar();}
  w=f?-w:w;
  return w;
}

void Pushup(int i){
  t[i].maxn=max(t[2*i].maxn,t[2*i+1].maxn);
  t[i].minn=min(t[2*i].minn,t[2*i+1].minn);
}

void Build(int i,int l,int r){
  t[i].l=l;t[i].r=r;
  if(l==r){t[i].maxn=t[i].minn=s0[l]-s1[l];return ;}
  int mid=(l+r)/2;
  Build(2*i,l,mid);Build(2*i+1,mid+1,r);
  Pushup(i);
}

int Query(int i,int l,int r,int k){
  if(t[i].l>=l&&t[i].r<=r){
    if(t[i].maxn<k||t[i].minn>k) return -1;
  }
  if(t[i].l==t[i].r){
    if(t[i].maxn==k) return t[i].l;
    else return -1;
  }
  int mid=(t[i].l+t[i].r)/2;
  if(mid>=l){
    int g=Query(2*i,l,r,k);
    if(g!=-1) return g;
  }
  if(mid<r){
    int g=Query(2*i+1,l,r,k);
    if(g!=-1) return g;
  }
  return -1;
}

void Get(int x){
  idx=0;max_pos=min_pos=sum0=0;
  while(x){
    p[++idx]=(x&1);
    if(p[idx]){
      max_pos=idx;
      if(!min_pos) min_pos=idx;
    }
    else if(min_pos) sum0++;
    x>>=1;
  }
  if(min_pos==max_pos) min_pos=0,sum0=0;
}

int Pow(int x,int y){
  if(y==0) return 1;
  if(y==1) return x;
  int h=Pow(x,y/2);
  if(y%2==0) return h*h%MOD;
  if(y%2==1) return h*h%MOD*x%MOD;
}

int lowbit(int x){return x&(-x);}

signed main(){
  n=read();q=read();
  cin>>s;s=" "+s;
  for(int i=1;i<=n;i++){
    s0[i]=s0[i-1];s1[i]=s1[i-1];
    if(s[i]=='0') s0[i]++;
    else s1[i]++;
  }
  Build(1,1,n);
  for(int i=1;i<=q;i++){
    l=read();r=read();x=read();
    Get(x);
    int fir_pos=Query(1,l,r,sum0+1+(s0[l-1]-s1[l-1]));
    if(fir_pos!=-1){
      int ans=Pow(2,idx+r-(fir_pos+l+sum0)/2);
      printf("%lld\n",ans);
    }
    else{
      if(s0[r]-s0[l-1]<=sum0){
        int ans1=Pow(2,max_pos-1);
        int ans2=x-ans1;
        for(int j=1;j<=s0[r]-s0[l-1];j++) ans2+=lowbit(ans2);
        int ans=((ans1*Pow(2,s1[r]-s1[l-1])%MOD)+ans2)%MOD;
        printf("%lld\n",ans);
      }
      else{
        int siz1=max_pos+s1[r]-s1[l-1];
        int siz2=max_pos+s0[r]-s0[l-1]-sum0-1;
        int ans=(Pow(2,siz1-1)+Pow(2,siz2-1))%MOD;
        printf("%lld\n",ans);
      }
    }
  }
  return 0;
}

过不了$x=2^a$和$x=2^a+2^b$的点，求hack!