讓我們來定義一個正確的括弧字串：

(i) 圓角括弧()與方括弧[]分別都是一個正確的括弧字串

(ii) 若 S 是個正確的括弧字串，則 (S) 與 [S] 也是正確的括弧字串。

(iii) 若 A 和 B 都是正確的括弧字串，則將他們接起來 AB 也是正確的括弧字串。

對於一個包含至少一對方括弧[]的正確的括弧字串，我們可以將這個字串所有方括弧的[以及]分別換成相同的圓左括弧(，這麼一來經過取代的字串就變成了壞掉的括弧字串。例如 (( 是由 []取代而來；((((())) 可能是由 ,(),(()),((([])))這四種字串取代而來。

現在給你一個壞掉的括弧字串，請問它是由多少種正確的括弧字串經過以上字串取代方式而產生呢？由於答案巨大，請輸出答案除以 1000000009 的餘數。