Maximum Matching

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Devu is very frustrated with the following problem. So, he wants your help in solving it.
Given a set: S = {1,2,3,....,N}
Make a bipartite graph having partites X and Y. Partite X will contain all permutations of Set S. Partite Y will contain all strings of length (N1) having characters ‘I’ and ‘D’ only. Note that number of vertices in partite X will be N! and 2^{(N1)} in partite Y.
Consider a vertex x in partite X and a vertex y in partite Y.
string y will be signature of permutation x if :
y[i] = ‘I’ => x[i] < x[i+1] && y[i] = ‘D’ => x[i] > x[i+1] …. for all i from 0 to N2.
There will be an edge between permutation x and string y if string y is the signature of the permutation x and weight of the edge will be the square of the inversion count in permutation x.
You need to find the maximum weighted matching in the given bipartite graph. As the answer can be very large, print it modulo M.
Input
 First line of the input contains integers T, denoting the number of test cases and M.
 Next T lines will be containing the value of N
Output
For each test case, print a single integer representing the answer of that test case.
Constraints
 2 ≤ M ≤ 10^{9}
Subtask #1: 8 points
 1 ≤ T ≤ 20, 2 ≤ N ≤8.
Subtask #2: 22 points
 1 ≤ T ≤ 20, 2 ≤ N ≤ 15.
Subtask #3: 70 points
 1 ≤ T ≤ 20, 2 ≤ N ≤ 2000
Example
Input: 2 1007 2 3 Output: 1 17
Explanation
For N=3, graph can be shown as below:
Author:  amitpandeykgp 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/MAXMATCH 
Tags  amitpandeykgp, combinatorics, dynamicprogramming, ltime24, medium 
Date Added:  20042015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, 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, SCM chicken, 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. 