All Tracks Problem

The suit life
Tag(s):

Ad-Hoc, Bit manipulation, Medium

Problem
Editorial
Analytics

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.

Constraints

1<= T <=100

1<= Size of N <=1000

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

Input

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.)

Output

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

Sample Input

2
11
001

Sample Output

6
4

Explanation:

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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

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