Dexter and his Blood Slides

All submissions for this problem are available.
Problem Statement
Dexter wants to fill a box having compartments in the form of a 3xN grid and he has blood slides of N different types to do that. Each compartment is to be filled with exactly one blood slide. An arrangement of the grid is considered beautiful if no two compartments of the same row or same column have the same type of blood slide.
The compartments of the first two rows are already filled and they don't violate the beautiful condition (one type of blood slide doesn't appear more than once on the same row or the same column).
Find how many different ways he can fill the 3rd row such that the resulting grid is beautiful. Two ways of filling the box are considered different if there is at least one compartment which is filled with a different type of blood slide.
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 A1, A2, ..., AN, where Ai(1 ≤ i ≤ N) is the type of the blood slide at column i of 1st row.
The next line contains N integers B1, B2, ..., BN, where Bi(1 ≤ i ≤ N) is the type of the blood slide at column i of 2nd row.
Output
For each test case, output the number of ways to fill the 3rd row such that the resulting grid is beautiful. Output the result modulo 1000000007.
Constraints
1 ≤ T ≤ 10 3 ≤ N ≤ 1000 A1, A2, ..., AN is a permutation of the numbers 1, 2, ..., N. B1, B2, ..., BN is a permutation of the numbers 1, 2, ..., N. Ai ≠ Bi ( 1 ≤ i ≤ N)Example
Input
2 4 3 1 2 4 2 4 1 3 4 2 4 1 3 1 3 2 4Output
2 4
Explanation
For the 1st case the valid ways to fill the 3rd row are: {1,3,4,2} and {4,2,3,1}.
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:  ratish1992 
Editorial  https://discuss.codechef.com/problems/PREE06 
Tags  desc2013, dynamicprogramming, hard, ratish1992 
Date Added:  12102013 
Time Limit:  0.221935 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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. 