Fake Graph Theory (Problem F, CS3233 Midterm Contest 2023, 2023)
Time limit: 1 sec
Memory limit: 1024 MB

# Problem Statement
> 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' \mod 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 \le n \le 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
```
2
```
# Sample Output #1
```
768
```

Sample inputs:
2

Sample outputs:
768

# Solution Analysis

By drawing the generated graphs, we can conclude that each connected component must be a cycle. Suppose we draw the graph such that $p$ adds edges on the left part of the graph, and $q$ adds edges on the right part. The edges $(i, i + 2n)$ will then connect vertices from the left and right parts.

Before we start, let’s ignore the permutations, and focus on the _set_ of edges formed by $p$ and $q$ instead. Note that for a fixed set of edges on _one half_ of the graph, there’s $n! \times 2^n$ permutations which result in this set of edges. The $n!$ factor comes from reordering the $n$ pairs $(p_i, p_{i+n})$, and the $2^n$ factor comes from swapping the first and second element of each pair. So, we can later multiply the final answer by $(n! \times 2^n)^2$.

First, let’s compute for a given $n$, how many sets of edges (in both halves of the graph) such that there is a single cycle. Denote this value as `cycle[n]`. Note that there are $2n$ vertices on each half of the graph, for a total of $4n$ vertices.

The base case is `cycle[0] = 1`. Next, we will count `cycle[n]` by first considering all possible sets of edges, then subtracting it by invalid sets of edges.

The number of possible sets of edges on one side is $(2n - 1)!! = (2n - 1) \times (2n - 3) \times \cdots \times 1$. We can visualize this as the following: the lowest-indexed vertex can pick $(2n - 1)$ possible other vertices for the edge. Then, after we remove these two vertices, there are $(2n - 3)$ possible other vertices for the new lowest-indexed vertex, and so on. Thus, the number of possible sets of edges on one side is $(2n - 1) \times (2n - 3) \times \cdots \times 1$. Since there are two halves, the total possible set of edges is $(2n - 1)!!^2$.

Consider the lowest-indexed vertex, and suppose it is in some cycle with $4k$ vertices (note that the number of vertices in a cycle is always a multiple of $4$), with $2k$ vertices on each side.

For this to be invalid, $1 \le 2k < 2n$ must hold. The number of invalid sets of edges where the cycle containing the lowest-indexed pair $(i, i + 2n)$ is `cycle[k] \times \binom{2n - 1}{2k - 1} \times (2n - 2k - 1)!!^2`. The $\binom{2n - 1}{2k - 1}$ factor is from choosing $2k - 1$ other pairs of vertices $(i, i + 2n)$ that are included in the cycle, and the $(2n - 2k - 1)!!^2$ factor is from the set of edges of the remaining vertices. Therefore, we have the following recurrence relation:

```math
\text{cycle}[n] = (2n - 1)!!^2 - \sum_{k = 1}^{n - 1} \text{cycle}[k] \times \binom{2n - 1}{2k - 1} \times (2n - 2k - 1)!!^2
```
After we have cycle, we can compute the answer as follows. Let’s iterate the cycle size $4k$, then it will contribute to the answer by $\text{cycle}[k] \times \binom{2n}{2k} \times (2n - 2k - 1)!!^2$. The $\binom{2n}{2k}$ factor comes from selecting $2k$ of the vertex pairs $(i, i + 2n)$ included in the cycle, and $(2n - 2k - 1)!!^2$ from allowing all sets of edges in the remaining vertices.

**Challenge**: Can you derive a generating function solution?

**Challenge**: Can you compute $\mathbb{E}[C^2]$, where $C$ is the number of components? What about $\mathbb{E}[C^3]$?

Special judge (C++ scorer):