Chefina and Prefix Suffix Sums

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JAN20/hindi/CHEFPSA.pdf), [Bengali](http://www.codechef.com/download/translated/JAN20/bengali/CHEFPSA.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JAN20/mandarin/CHEFPSA.pdf), [Russian](http://www.codechef.com/download/translated/JAN20/russian/CHEFPSA.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JAN20/vietnamese/CHEFPSA.pdf) as well. Chefina likes prefix and suffix sums, so Chef decided to give some to her as her birthday present. He created a sequence $a_1, a_2, \ldots, a_N$ and calculated its prefix sums $pre_1, pre_2, \ldots, pre_N$ (for each valid $i$, $pre_i$ is the sum of the first $i$ elements of $a$) and suffix sums $suf_1, suf_2, \ldots, suf_N$ (for each valid $i$, $suf_i$ is the sum of the last $i$ elements of $a$). He arranged the elements of these sequences in a gift box and went to Chefina's home. When Chefina opened the gift box, she found out that all the elements got shuffled when Chef was carrying the box. For each element, it is now impossible to determine if it belonged to the sequence $pre$ or $suf$ and what its index in the correct sequence was. The only thing we know is a sequence $x_1, x_2, \ldots, x_{2N}$, which contains all the elements of the sequences $pre$ and $suf$, in no particular order. Chefina is now curious about the number of initial sequences $a$ which Chef could have chosen, such that it is possible to obtain $x$ by shuffling the prefix and suffix sums of $a$. Help Chefina find this number. Since it could be very large, compute it modulo $1,000,000,007$. ### 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 $2N$ spaceseparated integers $x_1, x_2, \ldots, x_{2N}$. ### Output For each test case, print a single line containing one integer ― the number of possible initial sequences modulo $1,000,000,007$. ### Constraints  $1 \le T \le 10^6$  $1 \le N \le 10^5$  $x_i \le 10^9$ for each valid $i$  the sum of $N$ over all test cases does not exceed $2 \cdot 10^6$ ### Subtasks **Subtask #1 (20 points):**  $T \le 10$  $N \le 10$ **Subtask #2 (80 points):** original constraints ### Example Input ``` 4 1 1 1 1 0 0 2 4 3 1 4 3 5 3 7 10 5 10 ``` ### Example Output ``` 0 1 2 4 ```Author:  rishup_nitdgp 
Editorial  https://discuss.codechef.com/problems/CHEFPSA 
Tags  combinatorics, jan20, math, medium, rishup_nitdgp, rishup_nitdgp, vijju123 
Date Added:  20112019 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 