Problem Description

After just solving the problem of the power network, Ali is stuck again by a task from his leader.

As mentioned before, Ali’s country has $n$ cities. Now the country needs to build some trade routes between certain pairs of cities, so that any two cities in the whole country are connected directly or indirectly.

To save money, there can be at most one direct trade route between every pair of cities. For two route-building plans, if there exists a pair of cities such that whether a route is built between them is different in the two plans, then the two plans are different; otherwise, they are the same. Now you need to find how many different plans there are in total.

That is the problem troubling Ali. In other words, you need to count the number of simple (no multiple edges and no self-loops) labeled undirected connected graphs on $n$ vertices.

Since this number may be very large, you only need to output the number of plans modulo $1004535809$ ( $479 \times 2 ^{21} + 1$ ).

Input Format

Only one line containing one integer $n$.

Output Format

Only one line containing one integer, the number of plans $\bmod \space 1004535809$.

3

4

4

38

100000

829847355

Hint

Constraints
For $20\%$ of the testdata, $n \le 10$.
For $40\%$ of the testdata, $n \le 1000$.
For $60\%$ of the testdata, $n \le 30000$.
For $80\%$ of the testdata, $n \le 60000$.
For $100\%$ of the testdata, $n \le 130000$.

Source: the second homework of China CTT in $2013$.

Translated by ChatGPT 5