该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

树

题目描述

给定一个整数 $n$，求有 $n$ 个节点的有根树可能的形态个数。

输入格式

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

接下来 $t$ 行，每行一个整数 $n$。

输出格式

共 $t$ 行，每行一个整数，求可能形态个数。

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

1
3

9

1
323

283888610

数据范围

对于全部数据：

$t \le 10^4$

$n \le 10^9$

提示

粉红色节点为根。

样例 1：