我們知道包含N個(gè)元素的堆可以看成是一棵包含N個(gè)節(jié)點(diǎn)的完全二叉樹(shù)。
每個(gè)節(jié)點(diǎn)有一個(gè)權(quán)值。對(duì)于小根堆來(lái)說(shuō)，父節(jié)點(diǎn)的權(quán)值一定小于其子節(jié)點(diǎn)的權(quán)值。
假設(shè)N個(gè)節(jié)點(diǎn)的權(quán)值分別是1~N，你能求出一共有多少種不同的小根堆嗎？
例如對(duì)于N=4有如下3種：
1
/ \
2 3
/
4
1
/ \
3 2
/
4
1
/ \
2 4
/
3
由于數(shù)量可能超過(guò)整型范圍，你只需要輸出結(jié)果除以1000000009的余數(shù)。