Problem Description

Just after solving the power grid problem, Fox Li is once again stumped by a task from his superiors.

As mentioned earlier, Fox Li's country has $n$ cities. Now, the country needs to establish trade routes between certain pairs of cities to ensure that any two cities in the country are directly or indirectly connected.

To save money, there can be at most one direct trade route between any two cities. For two schemes of establishing routes, if there exists a pair of cities where the route establishment differs between the two schemes, then these schemes are considered different; otherwise, they are the same. You need to determine the total number of different schemes.

In other words, you are asked to find the number of simple (no multi-edges, no self-loops) labeled undirected connected graphs with $n$ vertices.

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

Input Format

A single integer $n$.

Output Format

A single integer, the number of schemes modulo $1004535809$.

Sample Input and Output

Sample Input #1

3

Sample Output #1

4

Sample Input #2

4

Sample Output #2

38

Sample Input #3

100000

Sample Output #3

829847355

Notes

Data Range

• For $20\%$ of the data, $n \le 10$
• For $40\%$ of the data, $n \le 1000$
• For $60\%$ of the data, $n \le 30000$
• For $80\%$ of the data, $n \le 60000$
• For $100\%$ of the data, $n \le 130000$

Problem Source: The second assignment of the 2013 Chinese National Training Team

见题面 Input 部分

见题面 Output 部分