T626668 整数划分
题目描述
对于一个正整数 $n$，我们定义两种不同的划分方式：
无限重复划分：允许每个正整数任意次数地出现在划分中。
不重复划分：每个正整数最多只能出现一次。
请你分别计算这两种情况下，正整数 $n$ 的不同划分个数。
输入格式
第一行是测试数据的数量 $M$ ($1 \le M \le 10$)。
接下来 $M$ 行，每行包含一个正整数 $n$ ($1 \le n \le 10000$)。
输出格式
对于每个测试数据，输出一行，包含两个整数，用空格隔开：
第一个整数是允许无限重复使用每个数时的划分数，
第二个整数是每个数最多使用一次时的划分数。
结果均对 $10^9 + 9$ 取模。
说明/提示
对于 $n=6$，两种划分数的具体说明如下：
无限重复使用情况下的所有划分（共 11 种）：
6
5 + 1
4 + 2
4 + 1 + 1
3 + 3
3 + 2 + 1
3 + 1 + 1 + 1
2 + 2 + 2
2 + 2 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1
（每个正整数可以使用任意次数）
每个数最多使用一次情况下的所有划分（共 4 种）：
6
5 + 1
4 + 2
3 + 2 + 1
（不允许出现重复数字，比如不能用两个 1）
### 数据范围与说明
$1 \le M \le 10$
$1 \le n \le 10000$
模数为 $10^9 + 9$