All Tracks Problem

The suit life

Ad-Hoc, Bit manipulation, Medium


Zack and Cody are desperate to go out and play but Mr. Moseby has made it clear that the twins cannot play until they solve this problem. They're supposed to find out the inversion count of an array A[0]..a[2^N-1], hence size of the array is a power of 2.

Now Cody knows from his lessons that given the array for every i < j, inversion count is total number of pairs such that A[i] > A[j] . Example : for array A={2, 0, 3, 1}, inversion count is 3, pairs being (2,0), (2,1) & (3,1).

To add to the twins' miseries Mr. Moseby has asked them to calculate the array on their own, given the condition A[i] = i(XOR)M for all 0 <= i <= (2^N)-1 and M is a binary number of exactly N bits. Since you have fun watching the twins busy in their mischief's, help them escape. Refer to explanation for more clarity.


1<= T <=100

1<= Size of N <=1000

Digits of M will be 0 or 1, since M is a binary number.


First line of input is T, number of test cases. It is followed by T lines each containing M in binary form. Length of M is exactly N bits (M may contain leading zeroes.)


For each test case print inversion count of array modulo 1000000007.

Sample Input


Sample Output



M = 11 (3 in decimal). Hence N is 2. Size of array is 4. Array A will be written as {0(XOR)3, 1(XOR)3, 2(XOR)3, 3(XOR)3 }. A= {3,2,1,0}. Inversion count of given array is 6.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:
View All Notifications