g545.
收納盒 (Storage Box)
內容
給定一個字串序列S，將所有的 '?' 替換成 '[' 或 ']'，請計算出有幾種組合符合括號序列
範例：
S = "?]??" -> [][] 一種
S = "??????" -> [][][], [[]][], [[][]], [][[]], [[[]]] 五種
輸入說明
第一行輸入1個正偶數N (2 ≤ N ≤ 2,000)
第二行包含1個長度為N的字串S，其中S只包含'[', ']', '?' 3種字元
輸出說明
輸出所有符合括號序列的數量 mod $10^9 + 7$
範例輸入
#1
4 [??]
範例輸出
#1
2
範例輸入
#2
6 ?]]?]?
範例輸出
#2
0
範例輸入
#3
30 ??????????????????????????????
範例輸出
#3
9694845
測資資訊：
記憶體限制：
512
MB
提示 ：
此題目測資分成三組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組 (20分)：S中不包含 '?' 字元。
第二組 (20分)：S中 '?' 字元的個數 ≤ 10。
第三組 (60分)：依題敘。
標籤: