内存限制：256 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：139
通过：43
我们知道包含N个元素的堆可以看成是一棵包含N个节点的完全二叉树。
每个节点有一个权值。对于小根堆来说，父节点的权值一定小于其子节点的权值。
假设N个节点的权值分别是1~N，你能求出一共有多少种不同的小根堆吗？
例如对于N=4有如下3种：
1
/ \
2 3
/
4
1
/ \
3 2
/
4
1
/ \
2 4
/
3
由于数量可能超过整型范围，你只需要输出结果除以1000000009的余数。