Problem F
Fake Graph Theory
SoCCat the Combinatorician is a very combinatoricky cat. Currently, SoCCat is challenging you to solve a combinatorics problem!
SoCCat challenges you to solve the following combinatorics problem:
Given a graph $G$ with $4n$ vertices, along with two permutations $p$ and $q$, each with size $2n$ on the set $\{ 1, 2, \ldots , 2n\} $.
Add the following $4n$ edges:

For each $i \in \{ 1, 2, 3, \ldots , 2n\} $, add an edge between vertices $i$ and $i + 2n$.

For each $i \in \{ 1, 2, 3, \ldots , n\} $, add an edge between vertices $p_ i$ and $p_{i + n}$.

For each $i \in \{ 1, 2, 3, \ldots , n\} $, add an edge between vertices $q_ i + 2n$ and $q_{i + n} + 2n$.
Suppose the permutations $p$ and $q$ are chosen uniformly at random among the $(2n)!$ possible permutations. Note that the permutations $p$ and $q$ are independent of each other. What is the expected number of connected components in the resulting graph?
Suppose the expected number of connected components in the resulting graph is $E$. Then, let $E’ = E \times (2n)! \times (2n)!$. It can be proven that $E’$ is always an integer. You are required to output the value of $E’ \bmod 1\, 000\, 003\, 233$.
In other words, you should output the sum of the number of connected components in the resulting graph, over all $(2n)! \times (2n)!$ possible permutations $p$ and $q$.
Input
The first line of input contains an integer $n$, as described in the problem statement ($1 \leq n \leq 3233$).
Output
Output a single integer, the value of $E’ \bmod 1\, 000\, 003\, 233$.
Notes
In the sample test case, there’s a $\frac{1}{3}$ chance that there are $2$ connected components, and $\frac{2}{3}$ chance that there is $1$ connected component.
Therefore, $E=\frac{1}{3} \times 2 + \frac{2}{3} \times 1 = \frac{4}{3}$, and the output should be $\frac{4}{3} \times (4!)^2 = 768$.
Sample Input 1  Sample Output 1 

2 
768 