洛谷的一个比赛里的题，没有头绪，大佬们可以讨论一下思路嘛。。。
题目描述
对于全国各大大学的男生寝室，总是有各种混乱的父子关系。
那么假设现在我们一个男生寝室有不同的 n 个人，每个人都至多有一个“爸爸”，可以有多个“儿子”，且有且只有一个人没有“爸爸”(毕竟是室长，还是要给点面子，当然了，室长人人当嘛)。
那么现在问题来了，对于一个有 n 个人的寝室，最多可能存在多少种父子关系，当然每个人之间都必须要有直接或间接的父子关系。
输入输出格式输入格式：
第一行一个 正整数 t，表示有组数据。
接下来 t 行，每行一个整数 n，表示有 n 个人。
输出格式：
共 t 行，每行一个整数，求关系个数。
由于答案可能较大，则我们需要输出答案对 1e9+9 取模的值。
输入输出样例
输入样例#1：
1
3
输出样例#1：
9
输入样例#2：
1
323
输出样例#2：
283888610
说明
对于 10% 的数据，保证 t=0t=0；
另有 30% 的数据，保证 n≤5n≤5；
对于 100% 的数据，t≤10^4t≤104，n≤10^9n≤109。
题目描述
对于全国各大大学的男生寝室，总是有各种混乱的父子关系。
那么假设现在我们一个男生寝室有不同的 n 个人，每个人都至多有一个“爸爸”，可以有多个“儿子”，且有且只有一个人没有“爸爸”(毕竟是室长，还是要给点面子，当然了，室长人人当嘛)。
那么现在问题来了，对于一个有 n 个人的寝室，最多可能存在多少种父子关系，当然每个人之间都必须要有直接或间接的父子关系。
输入输出格式输入格式：
第一行一个 正整数 t，表示有组数据。
接下来 t 行，每行一个整数 n，表示有 n 个人。
输出格式：
共 t 行，每行一个整数，求关系个数。
由于答案可能较大，则我们需要输出答案对 1e9+9 取模的值。
输入输出样例
输入样例#1：
1
3
输出样例#1：
9
输入样例#2：
1
323
输出样例#2：
283888610
说明
对于 10% 的数据，保证 t=0t=0；
另有 30% 的数据，保证 n≤5n≤5；
对于 100% 的数据，t≤10^4t≤104，n≤10^9n≤109。
