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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.TreeMap;
import java.util.TreeSet;
				 
				 
				 
				 
				 
				public class Solution1 implements Runnable
				{
				    static final long MOD = 1000000007;
				    static class InputReader
				    {
				        private InputStream stream;
				        private byte[] buf = new byte[1024];
				        private int curChar;
				        private int numChars;
				        private SpaceCharFilter filter;
				        private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
				 
				        public InputReader(InputStream stream)
				        {
				            this.stream = stream;
				        }
				        
				        public int read()
				        {
				            if (numChars==-1) 
				                throw new InputMismatchException();
				            
				            if (curChar >= numChars)
				            {
				                curChar = 0;
				                try 
				                {
				                    numChars = stream.read(buf);
				                }
				                catch (IOException e)
				                {
				                    throw new InputMismatchException();
				                }
				                
				                if(numChars <= 0)                
				                    return -1;
				            }
				            return buf[curChar++];
				        }
				     
				        public String nextLine()
				        {
				            String str = "";
				            try
				            {
				                str = br.readLine();
				            }
				            catch (IOException e)
				            {
				                e.printStackTrace();
				            }
				            return str;
				        }
				        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 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 double nextDouble() 
				        {
				            int c = read();
				            while (isSpaceChar(c))
				                c = read();
				            int sgn = 1;
				            if (c == '-') 
				            {
				                sgn = -1;
				                c = read();
				            }
				            double res = 0;
				            while (!isSpaceChar(c) && c != '.') 
				            {
				                if (c == 'e' || c == 'E')
				                    return res * Math.pow(10, nextInt());
				                if (c < '0' || c > '9')
				                    throw new InputMismatchException();
				                res *= 10;
				                res += c - '0';
				                c = read();
				            }
				            if (c == '.') 
				            {
				                c = read();
				                double m = 1;
				                while (!isSpaceChar(c)) 
				                {
				                    if (c == 'e' || c == 'E')
				                        return res * Math.pow(10, nextInt());
				                    if (c < '0' || c > '9')
				                        throw new InputMismatchException();
				                    m /= 10;
				                    res += (c - '0') * m;
				                    c = read();
				                }
				            }
				            return res * sgn;
				        }
				        
				        public String readString() 
				        {
				            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 boolean isSpaceChar(int c) 
				        {
				            if (filter != null)
				                return filter.isSpaceChar(c);
				            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
				        }
				     
				        public String next() 
				        {
				            return readString();
				        }
				        
				        public interface SpaceCharFilter 
				        {
				            public boolean isSpaceChar(int ch);
				        }
				    }
				     
				    public static void main(String args[]) throws Exception
				    {
				        new Thread(null, new Solution1(),"Solution",1<<26).start();
				    }   
				    static long gcd(long a, long b) 
				    { 
				      if (b == 0) 
				        return a; 
				      return gcd(b, a % b);  
				    } 
				    static long lcm(long a,long b) {
				    	return (a*b)/gcd(a,b);
				    }
				    ArrayList<Integer> adj[];
				    public void run() 
				    {
				    	InputReader sc = new InputReader(System.in);
						PrintWriter w = new PrintWriter(System.out);
						sieve();
						int n  =sc.nextInt();
						int q = sc.nextInt();
						char[] ch = sc.next().toCharArray();
						long[] prefix=  new long[n+1];
						for(int i = 1;i <= ch.length;i++){
							if(ch[i-1] == '1') {
								prefix[i] = prefix[i-1] + 1;
							}else {
								prefix[i] = prefix[i-1];
							}
						}
						for(int i = 0;i < q;i++) {
							int l = sc.nextInt();
							int r = sc.nextInt();
							long cnt = prefix[r] - prefix[l-1];
							long count = (r - l + 1);
							long one = power(2,count,MOD);
							long two = power(2,cnt,MOD);
							long three = (two - 1 + MOD) % MOD;
							long four = (power(two,MOD-2,MOD) * three) % MOD;
							long fans = (one * four) % MOD;
							w.println(fans);
						}
						
						w.close();
				    }
				    static final int MAXN = 1000001; 
				       
				    // stores smallest prime factor for every number 
				    static int spf[] = new int[MAXN]; 
				       
				    // Calculating SPF (Smallest Prime Factor) for every 
				    // number till MAXN. 
				    // Time Complexity : O(nloglogn) 
				    static void sieve() 
				    { 
				        spf[1] = 1; 
				        for (int i=2; i<MAXN; i++) 
				       
				            // marking smallest prime factor for every 
				            // number to be itself. 
				            spf[i] = i; 
				       
				        // separately marking spf for every even 
				        // number as 2 
				        for (int i=4; i<MAXN; i+=2) 
				            spf[i] = 2; 
				       
				        for (int i=3; i*i<MAXN; i++) 
				        { 
				            // checking if i is prime 
				            if (spf[i] == i) 
				            { 
				                // marking SPF for all numbers divisible by i 
				                for (int j=i*i; j<MAXN; j+=i) 
				       
				                    // marking spf[j] if it is not  
				                    // previously marked 
				                    if (spf[j]==j) 
				                        spf[j] = i; 
				            } 
				        } 
				    } 
				       
				    long one = 1;
				    long two = 0;
				    // A O(log n) function returning primefactorization 
				    // by dividing by smallest prime factor at every step 
				    void getFactorization(int x) 
				    { 
				        TreeMap<Integer,Integer> tmap = new TreeMap();
				        while (x != 1) 
				        { 
				        	if(tmap.containsKey(spf[x])) {
				        		tmap.put(spf[x],tmap.get(spf[x]) + 1);
				        	}
				        	else {
				        		tmap.put(spf[x],1);
				        	}
				            x = x / spf[x]; 
				        } 
				        TreeSet<Integer> toCalc = new TreeSet();
				        for(Integer key: tmap.keySet()) {
				        	one = one * key;
				        	two = Math.max(two,tmap.get(key));
				        	toCalc.add(tmap.get(key));
				        }
				        if(two == 1) {
				        	two = 0;
				        }
				        else if(two % 2 == 0) {
				        	int count = 0;
				        	if(toCalc.size() == 1) {
				        		int most = Integer.highestOneBit((int) two);
				        		if(most != two) {
						        	two = (Integer.highestOneBit((int) two) * 2);
						        	count++;
				        		}else {
				        			
				        		}
				        	}else {
				        		count++;
				        		int most = Integer.highestOneBit((int) two);
				        		if(most != two) {
						        	two = (Integer.highestOneBit((int) two) * 2);
				        		}else {
				        			
				        		}
				        	}
				        	while(two != 1) {
				        		two = two/2;
				        		count++;
				        	}
				        	
				        	two = count;
				        }else {
				        	two = (Integer.highestOneBit((int) two) * 2);
				        	int count = 0;
				        	while(two != 1) {
				        		two = two/2;
				        		count++;
				        	}
				        	count++;
				        	two = count;
				        }
				    } 
				    long[] fact = new long[100005];	
				    long nCr(int n,int r){ 
				    	long tmp1 = (fact[r] * fact[n-r]) % MOD;
				    	tmp1 = power(tmp1,MOD-2,MOD);
				    	long tmp2 = (fact[n] * tmp1) % MOD;
				    	return tmp2;
	 			    }
				    static long power(long a,long b,long mod) {
						long ans = 1;
						a = a % mod;
						while(b != 0) {
							if(b % 2 == 1) {
								ans = (ans * a) % mod;
							}
							a = (a * a) % mod;
							b = b/2;
						}
						return ans;
					}
				   void pre() {
					   fact[0] = 1;
					   for(int i = 1;i < 100005;i++) {
						   fact[i] = (fact[i-1] * i) % MOD;
					   }
				   }
				    class Pair implements Comparable<Pair>{
				        int a;
				        int b;
				        Pair(int a,int b){
				            this.b = b;
				            this.a = a;
				            
				        }
				        public boolean equals(Object o) {
				            Pair p = (Pair)o;
				            return this.a == p.a && this.b == this.b;
				        }
				        public int hashCode(){
				            return Long.hashCode(a)*27 + Long.hashCode(b)*31;
				        }
				        public int compareTo(Pair p) {
				            return Long.compare(this.a,p.a);
				        }
				    }
				    
				}