{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eScientist Aftab has made a groundbreaking discovery regarding chromosomal crossover today!\u003cbr\u003e \u003cbr\u003e 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 non-empty parts. \u0026nbsp;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,…,N-1] and the same for LB and RB. After applying crossover, we get two offspring O1\u003dLA+RB andO2\u003d LB+RA. Here ‘+’ is string concatenation operator.\u003c/p\u003e\r\n\u003cp\u003eScientist 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).\u003c/p\u003e\r\n\u003cp\u003eAlthough 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\u003csup\u003e9\u003c/sup\u003e+7 of the fittest offspring after applying crossover.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eInput starts with an integer \u003cstrong\u003eT(\u0026lt;\u003d30)\u003c/strong\u003e, denoting the number of test cases. Each case contains two lines containing two strings of same length \u003cstrong\u003eN (2\u0026lt;\u003dN\u0026lt;\u003d100000)\u003c/strong\u003e. Strings will contain only 0’s and 1’s.\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each case of input, print the case number followed by the decimal value modulo 10\u003csup\u003e9\u003c/sup\u003e+7 of the fittest string after the crossover.\u003c/p\u003e\r\n\u003ch3\u003eSample I/O\u003c/h3\u003e\r\n\u003ctable border\u003d\"1\" cellspacing\u003d\"0\" cellpadding\u003d\"0\"\u003e\r\n\u003ctbody\u003e\r\n\u003ctr\u003e\r\n\u003ctd width\u003d\"308\" valign\u003d\"top\"\u003e\r\n\u003cp\u003eInput\u003c/p\u003e\r\n\u003c/td\u003e\r\n\u003ctd width\u003d\"308\" valign\u003d\"top\"\u003e\r\n\u003cp\u003eOutput\u003c/p\u003e\r\n\u003c/td\u003e\r\n\u003c/tr\u003e\r\n\u003ctr\u003e\r\n\u003ctd width\u003d\"308\" valign\u003d\"top\"\u003e\r\n\u003cp\u003e2\u003c/p\u003e\r\n\u003cp\u003e100101\u003c/p\u003e\r\n\u003cp\u003e110010\u003c/p\u003e\r\n\u003cp\u003e10010\u003c/p\u003e\r\n\u003cp\u003e11101\u003c/p\u003e\r\n\u003c/td\u003e\r\n\u003ctd width\u003d\"308\" valign\u003d\"top\"\u003e\r\n\u003cp\u003eCase 1: 53\u003c/p\u003e\r\n\u003cp\u003eCase 2: 30\u003c/p\u003e\r\n\u003c/td\u003e\r\n\u003c/tr\u003e\r\n\u003c/tbody\u003e\r\n\u003c/table\u003e\r\n\u003cp\u003e\u0026nbsp;\u003c/p\u003e\r\n\u003ch3\u003eExplanation of Sample I/O\u003c/h3\u003e\r\n\u003cp\u003eFor the first case, the fittest offspring is 110101, whose decimal value modulo 10\u003csup\u003e9\u003c/sup\u003e+7 is 53.\u003c/p\u003e\n\u003c/div\u003e"}}]}