Catalan number的遞迴式定義：
$C_0 = 1$ and $\displaystyle C_n= \sum_{i=0}^{n-1} C_i \times C_{n-1-i}$ for $n \geq 1$
計算$C_n$ 除以 P 的餘數，P=1e9+9。
輸入一個非負整數n，n < 100。
$C_n$ 除以P的餘數
3
5
20
564120366