Background

A daily scene often seen in male dorms at universities:

$A:$ “I didn’t bring tissues. Hurry and save me in the restroom!”

$B:$ “Call me dad.”

$A:$ “Dad!”

$............................................$

$A:$ “I’m out of money. Can you lend me some?”

$B:$ “Call me dad.”

$A:$ “Dad!”

One month later,

$B:$ “Can you pay me back?”

$A:$ “Call me dad.”

$B:$ “Dad!”

Problem Description

In male dorms across the country, there are always all kinds of messy “father-son” relationships.

Now suppose a dorm has $n$ different people. Each person has at most one “dad”, can have multiple “sons”, and there is exactly one person who has no “dad” (after all, they are the dorm leader, so give them some respect; of course, anyone can be the leader).

Now the question is: for a dorm with $n$ people, what is the maximum possible number of different father-son relationships? Also, between any two people, there must be a direct or indirect father-son relationship.

Input Format

The first line contains a non-negative integer $t$, meaning there are $t$ test cases.

The next $t$ lines each contain an integer $n$, meaning there are $n$ people.

Output Format

Output $t$ lines. Each line contains one integer, the number of possible relationships.

Since the answer may be large, output the result modulo $10^9+9$.

1
3

9

1
323

283888610

Hint

• For $10\%$ of the testdata, it is guaranteed that $t=0$.

• For another $30\%$ of the testdata, it is guaranteed that $n \le 5$.

• For $100\%$ of the testdata, $t \le 10^4$, $1 \le n \le 10^9$.

Translated by ChatGPT 5