"Udd jaibu ye maina" is the song that "Long" loves a lot and hence keeps listening it throughout the day, as a result her room partner "Circuit" gets frustrated and kicks "Long" right in the face...fight begins.

To punish Circuit, Long slaps her and threatens to beat her till she replies to a problem.

Here goes the problem:-

There is a binary string (string composed of 0 and 1). Circuit will be asked questions Q number of times. Each time, Long will give two numbers i.e. A and B and circuit will have to flip the bits in the current string (i.e. each time updated string will be treated as current string) from the indices A to B (both inclusive).

NOTE:- Flipping means , turn 0 to 1 and vice-versa.

Input:- First line contains a String and then next line contains a integer Q. Next Q lines, contains A and B.

Output:-

Tell the Decimal value of current Binary String (after Q queries) i.e. if the binary string after Q queries becomes 101 then print 5 i.e. 1(2^2)+0(2^1)+1(2^0)=5.

Sum could be very large, hence print it modulo 1e9+9 i.e. 1000000009

Note:- Problem can be best solved when the song is played in background :p....https://www.youtube.com/watch?v=fkYI8t3kPCI

Constraints:-

1<=Length of STRING<=1000000

1<=Q<=10^6

0<=A<=B<=Length of String-1