Problem Statement   Note: This problem has a nonstandard time limit: 4 seconds.
You are given an undirected graph G1.
This graph has k vertices, numbered 0 through k1.
You are given the int k.
You are also given two equallylong int[]s a and b that describe the edges of G1.
For each i, there is an edge between a[i] and b[i].
Finally, you are given an int n.
Construct a new graph G2 as follows.
 Take n distinct copies of G1. We will call them "copy 0" through "copy n1".
 For each i, in copy i, increment the numbers of all vertices by i*k. After this change, the vertices in our graph have distinct numbers from 0 to (k*n1).
 Take the complement of the graph you currently have. I.e., a pair of vertices is connected by an edge after this step if and only if it wasn't connected before this step.
A Hamiltonian path in G2 is a path that visits each vertex of G2 exactly once.
The path may start and end in any vertex of G2.
The first and the last vertex of the path do not have to be connected by an edge.
Two paths differ if their sequences of visited vertices differ.
In particular, the path (0,1,2,3) differs from the path (3,2,1,0).
Count the number of Hamiltonian paths in G2.
Return that count modulo 998244353 (a prime number).
  Definition   Class:  HamiltonianPaths  Method:  countPaths  Parameters:  int, int[], int[], int  Returns:  int  Method signature:  int countPaths(int k, int[] a, int[] b, int n)  (be sure your method is public) 
    Constraints    k will be between 1 and 14, inclusive.    a will have between 0 and k*(k1)/2 elements, inclusive.    b will have exactly the same number of elements as a.    The graph described by the edges a,b will not have any selfloops or multiple edges.    n will be between 1 and 50,000, inclusive.   Examples  0)     Returns: 152  Our graph G1 looks as follows:
0  1  2
When constructing G2, we start by taking two copies of G1 and relabeling them:
0  1  2
3  4  5
Finally, we take the complement of this graph.
The result looks as follows:

 
0 1 2
\/\/
/\/\
3 4 5
 

The resulting graph does also contain the edges 05 and 23, these are not shown in the figure above.
Some examples of Hamiltonian paths in this graph:
 025314
 413520
 024135
 031425
 052314


 1)     Returns: 129246395  The final graph will be a complete graph with 12*10000 nodes. So, the answer in this case is (120000)! mod 998244353 = 129246395. 

 2)     3)     Returns: 1  The resulting graph G2 has a single isolated vertex 0.
There is exactly one Hamiltonian path: the path that starts in vertex 0 and ends immediately. 

 4)    4  {1,2,3,2,3,3}  {0,0,0,1,1,2}  1 
 Returns: 0  
 5)    4  {1,2,3,2,3,3}  {0,0,0,1,1,2}  10006 
 Returns: 33330626  
 6)    14  {0,4,0,0,0,12,2,2,9,2,2,3,3,3,3,4,8,4,5,5,10,11,6,12,10,13,10,13,12,13,11}  {2,0,5,8,11,1,5,6,2,10,12,4,5,9,13,7,4,13,6,7,5,5,8,7,8,8,9,9,10,10,13}  50000 
 Returns: 372837676  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
