Chef and The Colored Grid

All submissions for this problem are available.
The Chef wants to color a 3xN grid and he has N different types of colors to do that. Each cell of the grid has to be colored with exactly one color. A coloring of the grid is
considered beautiful if no two cells of the same row or same column have the same color.
The cells of first two rows are already colored and they don’t violate the beautiful condition (one color doesn’t appear more than once on the same row or on the same column).
Find how many different ways he can color the 3rd row such that the resulting grid is beautiful. Two ways of coloring are considered different if there is at least one cell which is colored with different color.
Input
The first line of the input contains an integer T denoting the number of test cases.
 The first line of each test
case contains an integer N.  The next line contains N integers A_{1}, A_{2}, ..., A_{N}, where A_{i}(1 ≤ i ≤ N) is the color of the cell at column i of 1st row.
 The next line contains N integers B_{1}, B_{2}, ..., B_{N}, where B_{i}(1 ≤ i ≤ N) is the color of the cell at column i of 2nd row.
Output
For each test case, output the number of ways to color the 3rd row such that the resulting grid is beautiful. Output the result modulo 1000000007.
Constraints
 1 ≤ T ≤ 20
 3 ≤ N ≤ 1000
 A_{1}, A_{2}, ..., A_{N} is a permutation of the numbers 1, 2, ..., N.
 B_{1}, B_{2}, ..., B_{N} is a permutation of the numbers 1, 2, ..., N.
 A_{i} ≠ B_{i} ( 1 ≤ i ≤ N)
Example
Input: 2 4 2 1 4 3 4 2 3 1 4 2 4 1 3 1 3 2 4 Output: 2 4
Explanation
For the 1st case the valid ways to color the 3rd row are: {1,3,2,4} and {3,4,1,2}.
For the 2nd case the valid ways are: {3,1,4,2} , {3,2,4,1} , {4,1,3,2} and {4,2,3,1}.
Author:  rustinpiece 
Tester:  rubanenko 
Editorial  http://discuss.codechef.com/problems/GRIDCOL 
Tags  combinatorics, cook37, hard, inclusnexclusn, rustinpiece 
Date Added:  5082013 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, CLOJ, 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. 