P10982 Connected Graph
Background
This problem is a simplified version of P4841 [CTT Homework 2013] City Planning, with the polynomial part from the original problem removed.
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$ ).
Explanation/Hint
Constraints: $1\leq n \leq 1000$.
Translated by ChatGPT 5