CROSSOVER  The Crossover
Scientist Aftab has made a groundbreaking discovery regarding chromosomal crossover today!
Before going into details let’s understand a few definitions first. According to Holland’s convention, a gene is represented by either 0 or 1. A chromosome is a string of genes. While in crossover, two parental chromosomes arbitrarily get separated at the exact same position forming four nonempty parts. And these parts join together to form two offspring. For example, let A and B be two parental chromosomes of length N. After cutting those at arbitrary position X, we get four parts LA, RA, LB, RB. Here LA is made of A[0,…,X], RA is made of A[X+1,…,N1] and the same for LB and RB. After applying crossover, we get two offspring O1=LA+RB andO2= LB+RA. Here ‘+’ is string concatenation operator.
Scientist Aftab’s claim is that, the fittest offspring among O1 and O2 is the one which is greater in value. Here the value of a chromosome is computed keeping in mind that this is a bitstring with the leftmost bit being the Most Significant Bit (MSB) and the rightmost bit is the Least Significant Bit (LSB).
Although scientist Aftab is a great genetics researcher, he is not good at handling chromosomes of large size. So he is seeking your help. You will be given two chromosomes of length N. And you will have to output the decimal value modulo 10^{9}+7 of the fittest offspring after applying crossover.
Input
Input starts with an integer T(<=30), denoting the number of test cases. Each case contains two lines containing two strings of same length N (2<=N<=100000). Strings will contain only 0’s and 1’s.
Output
For each case of input, print the case number followed by the decimal value modulo 10^{9}+7 of the fittest string after the crossover.
Sample I/O
Input 
Output 
2 100101 110010 10010 11101 
Case 1: 53 Case 2: 30 
Explanation of Sample I/O
For the first case, the fittest offspring is 110101, whose decimal value modulo 10^{9}+7 is 53.
hide comments
akshayvenkat:
20161108 20:14:28
@Sourav Sen Tonmoy, could you please check my submission? 25+ WA's now, its getting very frustrating. 

akshayvenkat:
20161107 02:45:46
I am getting every answer right for all randomly generated strings, the ones in toolkit, and also for the cases provided by @matematikaadit. Still getting WA. Can someone help? Is there any corner case?


:D:
20161001 20:31:33
Nice question. Requires careful analysis of all the scenarios. If anyone is having trouble with WA, please test with brute force. BF here is simply checking all valid partitions and getting the max value out of all of them. And since inputs are binary strings, you can quickly test all valid test cases up to length of 10 or so. It should guarantee you test all possible scenarios. Also remember partitions must be nonempty and we're looking for biggest value BEFORE modulo operation. 

Aditya Varshney:
20160603 09:39:03
Last edit: 20160603 10:30:18 

Ragini:
20160531 18:00:45
Last edit: 20160602 08:48:54 

matematikaadit:
20160506 09:18:01
For those who still got WA. Try a few simple test case below:


Vikneshwar E:
20160503 05:22:34
Last edit: 20160504 05:33:26 

it_is_me:
20160501 19:46:10
@Sourav Sen Tonmoy can you please tell some test where one might make mistakes getting WA again and again. 

naruto09:
20160428 12:16:45
@Sourav can you please check my submission once...I keep getting WA and TLE Last edit: 20160428 12:59:18 

Purav Shah:
20160428 10:27:46
@Sourav are the solutions rejudged, since my AC solution became WA. Please check submission ID 16825716.

Added by:  Sourav Sen Tonmoy 
Date:  20160425 
Time limit:  0.300s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Own problem. Used in NHSPC 2016 Final Round. More about NHSPC: http://www.nhspc.org/ 