SOLVE

LATER

The suit life

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,
Kotlin,
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Swift,
Visual Basic

Initializing Code Editor...

OTHER PROBLEMS OF THIS CHALLENGE

{"ed328e4": "/pagelets/problem-author-tester/algorithm/the-suit-life-86/", "e281379": "/pagelets/problems-hint/algorithm/the-suit-life-86/", "e604301": "/pagelets/show-submission/algorithm/the-suit-life-86/", "0a80c0b": "/pagelets/suggested-problems/algorithm/the-suit-life-86/", "1e72eea": "/pagelets/recommended-problems/algorithm/the-suit-life-86/"}

realtime.hackerearth.com

80

a4225a63fafafc7794f8efbc0e679c5c0d8d67bb

58a29e5cae2309f04b28

/realtime/pusher/auth/