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=10^9+9$。
輸入一個非負整數 $n$，$n < 100$。
$C_n$ 除以 $P$ 的餘數
3
5
20
564120366