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