Running King

In People's Republic Of Running, people are crazy about runnning. They keep a habit of running everyday, especially the Head King, because he isn't confident about his figure (please don't tell him~).

The Head King is going to build a new city, which contains $N$ towns. He want to build some bidirectional roads between some of the towns (each road connect two towns) and choose some of them to form his private running route. The Head King can't accept more than one bidirectional roads between two towns, because he has no sense of direction and it will make him bemused. He prefers enjoying the landscape changing while running, so he can't stand any same road on his running route.

Now, the Head King wants to know the total number of scheme of road constructing. Every scheme satisfies that there exist a town for him both to start and finish running(the running route contains at least one road). Please note the towns in the city needn't to be connected to each other.

First line contains $T(T \leq 10)$, the number of test cases.

For each case, there is one single line containing one non-negative integer $N(n \leq 2e5)$.

It is guarantee that there are at most one case in which $n \geq 1000$

For each test case, output a single number —— the number of schemes modulo the population of King's country($1004535809$).

3
2
3
4

0
1
26

In sample 1, the Head King can't design any scheme.
In sample 2, the Head King can build three roads:1-2, 2-3, 3-1, and he can start from town 1 (2 and 3 are also legal) and run along the route:1-2-3-1 (or 1-3-2-1).
In sample 3, one possible scheme is building 3 roads:1-3, 3-4, 4-1, and the Head King can start from town 3 and run along the route:3-1-4-3.

2016 ACM/ICPC Asia Regional Shenyang Online