Graph Coloring (easy version)
Contest: Educational Codeforces Round 142 (Rated for Div. 2)
Difficulty rating: 2700
Tags: combinatorics, dp, graphs

The only difference between the easy and the hard version is the constraint on $$$n$$$.

You are given an undirected complete graph on $$$n$$$ vertices. A complete graph is a graph where each pair of vertices is connected by an edge. You have to paint the edges of the graph into two colors, red and blue (each edge will have one color).

A set of vertices $$$S$$$ is red-connected if, for every pair of vertices $$$(v_1, v_2)$$$ such that $$$v_1 \in S$$$ and $$$v_2 \in S$$$, there exists a path from $$$v_1$$$ to $$$v_2$$$ that goes only through red edges and vertices from $$$S$$$. Similarly, a set of vertices $$$S$$$ is blue-connected if, for every pair of vertices $$$(v_1, v_2)$$$ such that $$$v_1 \in S$$$ and $$$v_2 \in S$$$, there exists a path from $$$v_1$$$ to $$$v_2$$$ that goes only through blue edges and vertices from $$$S$$$.

You have to paint the graph in such a way that:

- there is at least one red edge;
- there is at least one blue edge;
- for each set of vertices $$$S$$$ such that $$$|S| \ge 2$$$, $$$S$$$ is either red-connected or blue-connected, but not both.

Calculate the number of ways to paint the graph, and print it modulo $$$998244353$$$.

Input format:
The first (and only) line contains one integer $$$n$$$ ($$$3 \le n \le 5 \cdot 10^3$$$).

Output format:
Print one integer — the number of ways to paint the graph, taken modulo $$$998244353$$$.

Constraints:
Time limit: 5.5 s
Memory limit: 512.0 MB

Example input:
3

Example output:
6

Example input:
4

Example output:
50

Editorial:
Lemma: if an undirected graph is disconnected, then its complement is connected. Similarly, if its complement is disconnected, then the graph itself is connected.
Proof: suppose a graph is disconnected. Pick two vertices $$$x$$$ and $$$y$$$ from different components. Every vertex outside of $$$x$$$'s component is connected to $$$x$$$ in the complement, and every vertex outside of $$$y$$$'s component is connected to $$$y$$$ in the complement; the complement also contains the edge from $$$x$$$ to $$$y$$$, so all vertices in the complement graph belong to the single component.
Why do we need this lemma at all? We can treat the graph formed by blue edges as the complement to the graph formed by red edges. So, if the "red" graph is disconnected, then the "blue" graph is connected, so we don't need to consider the case when some set of vertices is connected by neither color. We only need to make sure that no set of vertices is connected by both colors.
Let $$$A_n$$$ be the answer for $$$n$$$. Every graph counted in $$$A_n$$$ is either red-disconnected or blue-disconnected; since there is a bijection between red-disconnected and blue-disconnected graphs (you can flip the colors of all edges to transform one type into the other), we will count only red-disconnected graphs and multiply it by $$$2$$$.
Let $$$B_n$$$ be the number of blue-connected graphs with $$$n$$$ vertices meeting the properties of the problem statement. It's easy to see that $$$A_n = 2 \cdot B_n$$$ if $$$n > 1$$$, otherwise $$$A_n = B_n$$$ (the case $$$n = 1$$$ is special because a graph on one vertex is both red-connected and blue-connected). To calculate $$$A_n$$$, let's iterate on $$$k$$$ — the number of vertices which are in the same "red" component as $$$1$$$. This component must be a red-connected graph which meets the problem statement, so the number of ways to build the graph on these $$$k$$$ vertices is $$$B_k$$$; there are $$$\frac{(n-1)!}{(k-1)!(n-k)!}$$$ ways to choose the vertices in the same component as $$$1$$$, and the remaining graph can be either red-connected or blue-connected, so the number of ways to build the remaining graph is $$$A_{n-k}$$$.
Thus, we get the following two relations:
$$$$$$B_{n} = \sum\limits_{k=1}^{n-1} B_k A_{n-k} \frac{(n-1)!}{(k-1)!(n-k)!}$$$$$$
$$$$$$A_n = 2 \cdot B_n \textrm{ if } n>1 \textrm{, otherwise } B_n$$$$$$
We can calculate all values with dynamic programming using these formulas in $$$O(n^2)$$$.