#P4981. 父子

父子

题目背景

上演在各大学男生寝室的日常 ::

A:A : “我没带纸,快来厕所救我!”

B:B : “叫爸爸。”

A:A : “爸爸!”

........................................................................................

A:A : “我没钱了,能借我点吗。”

B:B : “叫爸爸。”

A:A : “爸爸!”

一个月后、

B:B : “能把钱还给我吗。”

A:A : “叫爸爸。”

B:B : “爸爸!”

题目描述

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

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

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

输入格式

第一行一个 正整数 tt,表示有组数据。

接下来 tt 行,每行一个整数 nn,表示有 nn 个人。

输出格式

tt 行,每行一个整数,求关系个数。

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

1
3

9
1
323

283888610

提示

  • 对于 10%10\% 的数据,保证 t=0t=0

  • 另有 30%30\% 的数据,保证 n5n≤5

  • 对于 100%100\% 的数据,t104t≤10^4n109n≤10^9