Counting Connected Labeled Graphs

You are given a country with n cities. Trade routes are to be constructed between some pairs of cities such that the entire country is connected (i.e. every pair of cities is linked by a direct or indirect route). There can be at most one direct route between any two cities (no multiple edges and no self-loops). Two configurations are considered different if there exists at least one pair of cities where one configuration has a route and the other does not.

In other words, you are asked to count the number of simple (no self-loops, no multiple edges) undirected connected graphs on n labeled vertices.

As the answer can be extremely large, output it modulo $$1004535809 = 479 \times 2^{21} + 1.$$

A recurrence that computes the number of connected graphs is given by: $$f(1)=1, \quad f(n)=2^{\binom{n}{2}} - \sum_{i=1}^{n-1}\binom{n-1}{i-1}\,2^{\binom{n-i}{2}}\,f(i).$$

Note: \(\binom{n}{2}\) denotes the binomial coefficient representing the number of pairs among \(n\) cities.

inputFormat

The input consists of a single integer n (n ≥ 1) on one line.

outputFormat

Output the number of connected graphs on n labeled vertices modulo 1004535809.

sample

1

1