Problem: 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 n parts, places them on a row and numbers them from 1 through n. For each part i, he defines the deliciousness of the part as x_i ∈ \{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 i-th part then his enjoyment of the Banh-mi will increase by x_i and the deliciousness of all the remaining parts will also increase by x_i. The initial enjoyment of JATC is equal to 0.

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

However, JATC doesn't want to eat all the parts but to save some for later. He gives you q queries, each of them consisting of two integers l_i and r_i. 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 [l_i, r_i] in some order.

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

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 100 000).

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

Each of the following q lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) — the segment of the corresponding query.

Output

Print q lines, where i-th of them contains a single integer — the answer to the i-th query modulo 10^9 + 7.

Examples

Input

4 2
1011
1 4
3 4


Output

14
3


Input

3 2
111
1 2
3 3


Output

3
1

Note

In the first example: 

  * For query 1: One of the best ways for JATC to eats those parts is in this order: 1, 4, 3, 2. 
  * For query 2: Both 3, 4 and 4, 3 ordering give the same answer. 



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

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main
{	
   static long mod=(long)(1e+9 + 7);
   //static long mod=(long)998244353;
   
   static int[] sieve;
   static ArrayList<Integer> primes;
   static PrintWriter out;
   static fast s;
   static StringBuilder fans;
   
   public static void solve()
   {
   	int n=s.nextInt();
   	int q=s.nextInt();
   	
   	String str=s.nextLine();
   	
   	int a[]=new int[n];
   	for(int i=0;i<n;i++) a[i]=str.charAt(i)-'0';
   	
   	int ones[]=new int[n];
   	
   	if(a[0]==1) ones[0]=1;
   	for(int i=1;i<n;i++) if(a[i]==0) ones[i]=ones[i-1]; else ones[i]=ones[i-1]+1;
   	
   	for(int i=0;i<q;i++)
   		{
   			int l=s.nextInt()-1;
   			int r=s.nextInt()-1;
   			
   			long cur_o=(long)ones[r]-((l>0)?ones[l-1]:0);
   			long cur_z=((long)(r-l+1))-cur_o;
   			
   			long ans1=(s.pow((long)2, cur_o, mod)-1+mod)%mod;
   			long ans2=(ans1*(s.pow((long)2, cur_z, mod)-1+mod)%mod)%mod;
   			fans.append(((ans1+ans2)%mod)+"\n");
   		}
   }
   
   public static void main(String[] args) throws java.lang.Exception
   {	  	
	     s = new fast();
	     out=new PrintWriter(System.out);
	     fans=new StringBuilder("");
		  
	     int t=1;
	     
	     while(t>0)
	    	 {
	    		 solve();
	    		 t--;
	    	 }
	    
	    out.println(fans);
	    out.close();
   }
  
 
 
static class fast {   
	
	   private InputStream i;
		private byte[]  buf = new byte[1024];
		private int curChar;
		
		private int numChars;
		
		//Return floor log2n
		public static long log2(long bits) // returns 0 for bits=0
			{
			    int log = 0;
			    if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
			    if( bits >= 256 ) { bits >>>= 8; log += 8; }
			    if( bits >= 16  ) { bits >>>= 4; log += 4; }
			    if( bits >= 4   ) { bits >>>= 2; log += 2; }
			    return log + ( bits >>> 1 );
			}
		
		public static boolean next_permutation(int a[])
		   {
			   int i=0,j=0;int index=-1;	   
			   int n=a.length;
			   
			   for(i=0;i<n-1;i++)
				   if(a[i]<a[i+1]) index=i;
			   
			   if(index==-1) return false;
			   i=index;
 
			  
			   for(j=i+1;j<n && a[i]<a[j];j++);
 
			   int temp=a[i];
			   a[i]=a[j-1];
			   a[j-1]=temp;
			   	   
			   for(int p=i+1,q=n-1;p<q;p++,q--)
			   {
				   temp=a[p];
				   a[p]=a[q];
				   a[q]=temp;
			   }
			   
			   return true;
		   }
		   
		   
		public static void division(char ch[],int divisor)
		   {
			   int div=Character.getNumericValue(ch[0]); int mul=10;int remainder=0;
			   StringBuilder quotient=new StringBuilder("");
			   for(int i=1;i<ch.length;i++)
			   {
				   div=div*mul+Character.getNumericValue(ch[i]);	
				   if(div<divisor) {quotient.append("0");continue;}
				   quotient.append(div/divisor);
				   div=div%divisor;mul=10;
				   
			   } 
			   remainder=div;
			   while(quotient.charAt(0)=='0')quotient.deleteCharAt(0);	   
			   System.out.println(quotient+" "+remainder);	  
		   }
		
		public static void sieve(int size)
		{
			sieve=new int[size+1];
			
			primes=new ArrayList<Integer>();
			
			sieve[1]=1;
			
			for(int i=2;i*i<=size;i++)
			{
				if(sieve[i]==0)
				 {
					for(int j=i*i;j<size;j+=i) {sieve[j]=1;}
				 }
			}
			
			for(int i=2;i<=size;i++)
			{
				if(sieve[i]==0) primes.add(i);
			}
		}
		
		public static long pow(long n, long b, long MOD)
		   {
		       long x=1;long y=n; 
		       while(b > 0)
		       {
		           if(b%2 == 1)
		           {
		               x=x*y;
		               if(x>MOD) x=x%(MOD);
		           }
		           y = y*y;
		           if(y>MOD) y=y%(MOD); 
		           b >>= 1;
		       }
		       return x;
		   }
 
 
		public static long mod_inv(long n,long mod)
		{
			return pow(n,mod-2,mod);
		}
		
		//Returns index of highest number less than or equal to key
		 public static int upper(long[] a,int length,long key)
		 {
			    int low = 0;
		        int high = length-1;
		        int ans=-1;
		        
		        while (low <= high) {
		            int mid = (low + high) / 2;
		            if (key >= a[mid]) {
		                ans=mid;
		            	low = mid+1;
		            } else if(a[mid]>key){
		                high = mid - 1;
		            }
		        }
		        return ans;
		}
		
		//Returns index of least number greater than or equal to key
		 public static int lower(long[] a,int length,long key)
		 {
			    int low = 0;
		        int high = length-1;
		        int ans=-1;
		        
		        while (low <= high) {
		            int mid = (low + high) / 2;
		            if (key<=a[mid]) {
		                ans=mid;
		            	high = mid-1;
		            }
		            else{
		            		low=mid+1;
		            	}
		        }
		        return ans;
		} 
		   
		public long gcd(long r,long ans)
		{
			if(r==0) return ans;
			return gcd(ans%r,r);
		}
		public fast() {
			this(System.in);
		}
		public fast(InputStream is) {
			i = is;
		}
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = i.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
		public String nextString() {
     		int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
 
	}	
}