父子(Father and Son)

对于全国各大大学的男生寝室，总是有各种混乱的父子关系。

那么假设现在我们一个男生寝室有不同的 $n$ 个人，每个人都至多有一个“爸爸”，可以有多个“儿子”，且有且只有一个人没有“爸爸”(毕竟是室长，还是要给点面子，当然了，室长人人当嘛)。

那么现在问题来了，对于一个有 $n$ 个人的寝室，最多可能存在多少种父子关系，当然每个人之间都必须要有直接或间接的父子关系。

第一行一个非负整数 $t$ ，表示有 $t$ 组数据。

接下来 $t$ 行，每行一个整数 $n$ ，表示有 $n$ 个人。

共 $t$ 行，每行一个整数，求关系个数。

由于答案可能较大，则我们需要输出答案对 $10^9+9$ 取模的值。

1
3

1
323

283888610

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1450。

Subtask	分值	测试点编号	说明
0	10	1~2	样例
1	25	3~8	小规模 n≤5 / 特殊: n=1(唯一室长答案为1), n=2(答案为2)
2	20	9~14	中等规模 t≤1000,n≤10^6 / Hack: n=10^9+9(底数恰为模数10^9+9倍数答案为0)
3	25	15~20	满规模 t=10000,n≤10^9 有根标号树计数 n^(n-1) mod (10^9+9) 压力测试
4	20	21~25	满规模 t=10000,n≈10^9 极值与边界综合回归

出处：原题链接

#P4981. 父子(Father and Son)