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.util.*;
import java.io.*;
import java.math.BigInteger;
import java.util.regex.*;

public class Codeforces{
	
	static class MyScanner{
		BufferedReader br;
		StringTokenizer st;
		
		MyScanner(FileReader fileReader){
			br = new BufferedReader(fileReader);
		}
		
		MyScanner(){
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		String nn(){
			while(st == null || !st.hasMoreElements()){
				try{
					st = new StringTokenizer(br.readLine());
				}catch(IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		String nextLine(){
			String s = "";
			try{
				s = br.readLine();
			}catch(IOException e){
				e.printStackTrace();
			}
			return s;
		}
		
		int ni(){
			return Integer.parseInt(nn());
		}
		
		long nl(){
			return Long.parseLong(nn());
		}
		
		double nd(){
			return Double.parseDouble(nn());
		}
	}
	
	private static PrintWriter out;
	
	public static void main(String[] args) throws FileNotFoundException{
		
		// Input from file
		// File inputFile = new File("JavaFile.txt");
		// File outputFile = new File("JavaOutputFile.txt");
		// FileReader fileReader = new FileReader(inputFile);
		// Here it ends
			
		MyScanner sc = new MyScanner();
		// MyScanner sc = new MyScanner(fileReader);
		
		out = new PrintWriter(new BufferedOutputStream(System.out)); // Output to console
		// out = new PrintWriter(new PrintStream(outputFile)); // Output to file
		
		int n = sc.ni(), q = sc.ni();
		char[] ar = sc.nn().toCharArray();
		int[] zero = new int[n + 1];
		int[] one = new int[n + 1];
		
		for(int i = 0; i < n; i++){
			if(ar[i] == '0') zero[i] = 1;
			else one[i] = 1;
		}
		
		for(int i = 1; i < n; i++){
			one[i] += one[i - 1];
			zero[i] += zero[i - 1];
		}
		
		final long MOD = 1_000_000_007;
		
		long power[] = new long[n + 1];
		power[0] = 1;
		for(int i = 1; i <= n; i++) power[i] = (2 * power[i - 1]) % MOD;
		
		while(q-- > 0){
			int x = sc.ni() - 1, y = sc.ni() - 1;
			int curOne = one[y] - (x - 1 >= 0? one[x - 1]: 0);
			int curZero = zero[y] - (x - 1 >= 0? zero[x - 1]: 0);
			
			// System.out.println(curOne + " " + curZero);
			
			long one1 = ((power[curOne] - 1) % MOD + MOD) % MOD;
			long two =  one1 * (((power[curZero] - 1) % MOD + MOD) % MOD) % MOD;
			long ans = (one1 + two) % MOD;
			
			out.println(ans);
		}
		
		out.close();
	}
}