Big Number

All submissions for this problem are available.
Given a binary represantation of number N. You are to find how many numbers from 0 to N have even number of ones in their binary represantation.
There is also an update operation, update (L,R), which means that all bits of N from L^{th} to R^{th} are flipped, i.e. ones to zeroes and vice versa. You have to also find the answer after each of these updates.
Input
The first line of input file contains binary represantation of number N. The second line contains number M  the number of update queries. Then M lines follow that describe each update query by two numbers  L and R. Note that the digits of N are numbered from left to right. That is, the leftmost(most significant) bit is numbered 1.
Output
Output the answer for initial value of N and also after each of the M updates modulo 10^{9}+7 in separate lines.
Constraints
 1 ≤ L ≤ R ≤ number of bits in N ≤ 10^{6}
 1 ≤ M ≤ 10^{5}
 all digits of N are either '0' or '1'.
Example
Input: 000 5 3 3 2 3 3 3 2 3 1 3 Output: 1 1 1 2 1 4
Explanation
After the final operation, N becomes 7. All numbers in range [0..7] that have even number of ones in their binary representation are: 0, 3, 5 and 6.
Author:  rubanenko 
Tester:  utkarsh_lath 
Editorial  http://discuss.codechef.com/problems/RRBIGNUM 
Tags  Rubanenko, cook38, medium, segmenttrees 
Date Added:  21092013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 