1062C.md (2663B)
1 Source: https://codeforces.com/problemset/problem/1062/C 2 3 C. Banh-mi 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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 \in \{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$. 24 25 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$. 26 27 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. 28 29 All the queries are independent of each other. Since the answer to the query could be very large, print it modulo $10^9+7$. 30 31 Input 32 33 The first line contains two integers $n$ and $q$ ($1 \le n, q \le 100\,000$). 34 35 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. 36 37 Each of the following $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the segment of the corresponding query. 38 39 Output 40 41 Print $q$ lines, where $i$-th of them contains a single integer — the answer to the $i$-th query modulo $10^9 + 7$. 42 43 Examples 44 45 Input 46 47 ``` 48 4 2 49 1011 50 1 4 51 3 4 52 ``` 53 54 Output 55 56 ``` 57 14 58 3 59 ``` 60 61 Input 62 63 ``` 64 3 2 65 111 66 1 2 67 3 3 68 ``` 69 70 Output 71 72 ``` 73 3 74 1 75 ``` 76 77 Note 78 79 In the first example: 80 81 * For query $1$: One of the best ways for JATC to eats those parts is in this order: $1$, $4$, $3$, $2$. 82 * For query $2$: Both $3$, $4$ and $4$, $3$ ordering give the same answer. 83 84 In the second example, any order of eating parts leads to the same answer.