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.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;


public class Main {
	public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }
	
	static class SegmentTree {
		private class SegmentNode {
			int val;
			int left;
			int right;
			SegmentNode leftChild;
			SegmentNode rightChild;
			public SegmentNode(int val, int left, int right) {
				super();
				this.val = val;
				this.left = left;
				this.right = right;
				this.leftChild = null;
				this.rightChild = null;
			}
			@Override
			public String toString() {
				return "SegmentNode [val=" + val + ", left=" + left + ", right=" + right + ", leftChild=" + leftChild
						+ ", rightChild=" + rightChild + "]";
			}
			
		}
		
		private SegmentNode root;
		public SegmentNode getRoot() {
			return root;
		}
		public void setRoot(SegmentNode root) {
			this.root = root;
		}
		public void createSegmentTree(char A[]) {
			root = createSegmentTree(0, A.length - 1, A);
		}
		private SegmentNode createSegmentTree(int left, int right, char A[]) {
			if(left > right) return null;
			int val = 0;
			if(A[left] == '1') val =1;
			SegmentNode root = new SegmentNode(val, left, right);
			if(left == right) {
				return root;
			}
			int mid = (left+right)/2;
			root.leftChild = createSegmentTree(left, mid, A);
			root.rightChild = createSegmentTree(mid + 1, right, A);
			root.val = root.leftChild.val + root.rightChild.val;
			
			return root;
		}
		public void updateSingleNode(int pos, int val) {
			updateSingleNode(pos, val, root);
		}
		// single node add 
		private void updateSingleNode(int pos, int val, SegmentNode root) {
			if(root.left == root.right) {
				root.val += val;
				return;
			}
			int mid = (root.left + root.right) / 2;
			if(pos <= mid) updateSingleNode(pos, val, root.leftChild);
			else updateSingleNode(pos, val, root.rightChild);
			root.val = root.leftChild.val + root.rightChild.val;
		}
		public int queryInterval(int l, int r) {
			return queryInterval(l, r, root);
		}
		// query interval sum 
		private int queryInterval(int l, int r, SegmentNode root) {
			int sum = 0;
			if(root.left >= l && root.right <= r) {
				sum += root.val;
				return sum;
			}
			int mid = (root.left + root.right) / 2;
			if(l > mid) sum += queryInterval(l, r, root.rightChild);
			else if(r <= mid) sum += queryInterval(l, r, root.leftChild);
			else sum += (queryInterval(l, r, root.rightChild) + queryInterval(l, r, root.leftChild));
			return sum;
		}
		
		@Override
		public String toString() {
			return "SegmentTree [root=" + root + "]";
		}
		
		
	}
	
	static class Task {
        private static final int maxl = 1000000007;
        long powerMod(long a, long b, long c)
        {
        	long ans = 1;
            a = a % c;
            while(b>0) {
                if(b % 2 == 1)
                ans = (ans * a) % c;
                b = b/2;
                a = (a * a) % c;
            }
            return ans;
        }
        public void solve(int testNumber, InputReader in, PrintWriter out) {
        	int n = in.nextInt();
        	int m = in.nextInt();
        	int a[] = new int[m];
          	int b[] = new int[m];
        	String string = in.next();
        	int one, zero;
        	for(int i=0;i<m;i++) {
        		a[i] = in.nextInt();
        		b[i] = in.nextInt();
        	}
        	char[] nodeArray = new char[n];
        	for(int i=0;i<n;i++) {
        		nodeArray[i] = string.charAt(i);  
        		
        	}
        	SegmentTree segmentTree = new SegmentTree();
    		segmentTree.createSegmentTree(nodeArray);
    		
        	for(int i=0;i<m;i++) {
        		a[i] --;b[i]--;
        		zero = 0;one = 0;
        		one = segmentTree.queryInterval(a[i], b[i]);
        		zero = b[i] - a[i] + 1 - one;
        		long z = powerMod(2, zero, maxl);
        		long o = powerMod(2, one, maxl);
           		long ans = z*(o-1);
           		ans%=maxl;
           		out.println(ans);
        	}
        }
    }
	static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        
        public long nextLong() {
            return Long.parseLong(next());
        }
        
        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}