Background

This problem is a simplified version of P4841 [CTT Homework 2013] City Planning, with the polynomial part from the original problem removed.

Problem Description

Find the number of labeled undirected connected graphs with $n$ vertices.

Input Format

Input one positive integer $n$.

Output Format

Output the answer modulo $1004535809$ ( $479 \times 2 ^{21} + 1$ ).

3

4

4

38

Hint

Constraints: $1\leq n \leq 1000$.

Translated by ChatGPT 5