All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/DEC19/hindi/BINXOR.pdf), [Bengali](http://www.codechef.com/download/translated/DEC19/bengali/BINXOR.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/DEC19/mandarin/BINXOR.pdf), [Russian](http://www.codechef.com/download/translated/DEC19/russian/BINXOR.pdf), and [Vietnamese](http://www.codechef.com/download/translated/DEC19/vietnamese/BINXOR.pdf) as well. You are given two binary strings $A$ and $B$, each with length $N$. You may reorder the characters of $A$ in an arbitrary way and reorder the characters of $B$ also in an arbitrary (not necessarily the same) way. Then, you should compute the XOR of the resulting strings. Find the number of distinct values of this XOR which can be obtained, modulo $1,000,000,007$ ($10^9 + 7$). ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains a single integer $N$. - The second line contains a single string $A$ with length $N$. - The third line contains a single string $B$ with length $N$. ### Output For each test case, print a single line containing one integer ― the number of unique XORs modulo $1,000,000,007$. ### Constraints - $1 \le T \le 10^5$ - $1 \le N \le 10^5$ - $|A| = |B| = N$ - $A$ and $B$ contain only characters '0' and '1' - the sum of $N$ over all test cases does not exceed $2 \cdot 10^5$ ### Subtasks **Subtask #1 (10 points):** - $N \le 5$ - the sum of $N$ over all test cases does not exceed $10$ **Subtask #2 (30 points):** - $N \le 1,000$ - the sum of $N$ over all test cases does not exceed $2 \cdot 10^3$ **Subtask #3 (60 points):** original constraints ### Example Input ``` 1 2 00 10 ``` ### Example Output ``` 2 ``` ### Explanation **Example case 1:** The characters in each string can be reordered in two ways (swap them or do nothing), so there are four values of their XOR: - "00" XOR "10" is "10" - "00" XOR "01" is "01" - "00" XOR "10" is "10" - "00" XOR "01" is "01" There are only two distinct values.
|Tags||binary, black_truce, dec19, easy, melfice, modulo|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.