a150. TOI 2021/10 潛力組：收納盒

題目描述

給定只包含「[」、「]」和「?」的字串。每個問號都必須替換成一個左括號或右括號。替換完成後，若由左到右任一前綴的左括號數都不少於右括號數，且整串左右括號數相同，就稱為合法括號序列。請計算可以得到多少個合法序列。

輸入格式

第一行為偶數 N，第二行為長度 N 的字串 S。 2 ≤ N ≤ 2000；S 的每個字元都是「[」、「]」或「?」。

輸出格式

輸出合法替換方法數除以 1000000007 的餘數。

來源

TOI 2021/10/25~2021/10/29 潛力組〈收納盒〉。本題以自寫文字重述規則，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202110/Storage%20Box.pdf