DMOPC '19 Contest 6 P3 - Grade 11 Math

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Serena is learning about binary numbers in math class! She is given a binary number S, and she is also given series of M operations which she must perform on it. In one operation, she sets all bits in the 1-indexed range [l,r] to 1, and outputs the base-10 value of the binary number, modulo 10^9+7.

The base-10 value of a binary number S of length n consisting of digits 0 and 1 is given by the sum of S_i \times 2^{n-i} over all i in [1, n].

Input Specification

The first line contains two space-separated integers, |S| and M, the length of the number and the number of operations.
The next line contains S, the original binary number.
The next M lines contain two space-separated integers, l and r, representing an operation described in the problem statement.

Output Specification

For each operation, output the base-10 value of the binary number after performing the operation, modulo 10^9+7.


In all subtasks,
1 \leq |S| \leq 500\,000
1 \leq l \leq r \leq |S|
0 \leq M \leq 500\,000

Subtask 1 [20%]

1 \leq |S| \leq 20

Subtask 2 [80%]

No additional constraints.

Sample Input 1

5 2
1 3
2 4

Sample Output 1



There are no comments at the moment.